首先分析每一次操作，我们发现这些操作有两个重要的特征：
- 互相独立
- 操作过程中每一个 a i a_i ai 单调不减
由此我们可以分析出，每一个 a i a_i ai 要么一直操作到 a i = b i a_i=b_i ai=bi，要么不动，这很像一个背包，考虑如何转化。
我们发现对于相同的 b i b_i bi，最优操作的步数一定相同（特征 1），令 p i p_i pi 表示将 1 变换成 i i i 的最少次数，那么此时我们有 n n n 个物品，第 i i i 个代价为 p b i p_{b_i} pbi，价值为 c i c_i ci，这就变成了一个普通的背包问题，我们考虑 p p p 的计算。
首先猜到动态规划，出题人非常善良，告诉我们 b i ≤ 1000 b_i\le 1000 bi≤1000， 也就是 p p p 允许在 O ( n 2 ) O(n^2) O(n2) 的复杂度下计算。
转移很显然，对于 p i p_i pi 我们枚举 j j j。将 p i + ⌊ i j ⌋ p_{i+\lfloor \frac{i}{j} \rfloor} pi+⌊ji⌋ 的值更新为 min { p i + ⌊ i j ⌋ , p i + 1 } \min\{p_{i+\lfloor \frac{i}{j} \rfloor},p_i+1\} min{pi+⌊ji⌋,pi+1} 即可。复杂度 O ( n 2 ) O(n^2) O(n2)，但是 ⌊ i j ⌋ \lfloor \frac{i}{j} \rfloor ⌊ji⌋ 对于不同的 j j j 有很多是重复的，所以我们可以使用数论分块优化到 O ( n n ) O(n\sqrt{n}) O(nn )。
接下来还剩最后一个问题，我们的背包容量是 k ≤ 1 0 6 k\le10^6 k≤106，物品数量最多是 n = 1000 n=1000 n=1000。显然会超时，神奇海螺告诉聪明的你其实物品的代价 p b i ≤ 12 p_{b_i}\le 12 pbi≤12，可以先算出来 p p p 然后利用魔法取最大得到这个结论，其实也很好理解，因为如果我们每次操作的 x = 1 x=1 x=1 的话，那么相当于倍增，所以这玩意最大差不多就是 lg \lg lg 级别的。
于是我们快乐地搞完了这题。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define cmin(a, b) (a)=min((a), (b))
#define cmax(a, b) (a)=max((a), (b))
#define mem(a, x) memset(a, x, sizeof(a))
#define rps(i, b, e) for(int i=(b);i<=(e);i++)
#define prs(i, e, b) for(int i=(e);i>=(b);i--)
#define rpg(i, g, x) for(int i=g.head[x];i;i=g.e[i].nxt)
#define opf(s) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
using namespace std;
template<class T>
inline void read(T &x) {
x=0;
bool f=false;
char c=getchar();
while(!isdigit(c))f|=(c=='-'), c=getchar();
while(isdigit(c))x=x*10+(c-'0'), c=getchar();
if(f)x=-x;
}
//前面这一坨请自动忽略
const int NR=1010, NN=1e3, STEP=12;
int T, n, k, w[NR], v[NR], dp[NR], f[STEP*NN+10];
//dp[i]=p[i]
void prework() {
mem(dp, 999999);
dp[1]=0;
rps(i, 1, NN)
rps(j, 1, i)
if(i+i/j<=NN)
cmin(dp[i+i/j], dp[i]+1);
}
int main() {
prework();
read(T);
while(T--) {
read(n), read(k);
int trk=0, sum=0;
rps(i, 1, n)read(w[i]), w[i]=dp[w[i]], trk+=w[i];
rps(i, 1, n)read(v[i]), sum+=v[i];
if(k>=trk) {
printf("%d\n", sum);
continue;
}
mem(f, 0);
rps(i, 1, n)prs(j, k, w[i])
cmax(f[j], f[j-w[i]]+v[i]);
printf("%d\n", f[k]);
}
return 0;
}