(D) Сделай равными (Codeforcces)

#include <bits/stdc++.h>

using namespace std;

const int N = 1e3 + 5;
const int inf = 1e9;

int d[N];

int main(){
    for (int i = 0; i < N; i++) {
        d[i] = inf;
    }
    d[1] = 0;
    for (int i = 1; i < N; i++) {
        for (int x = 1; x <= i; x++) {
            int j = i + i / x;
            if (j < N) {
                d[j] = min(d[j], d[i] + 1);
            }
        }
    }

    int T;
    cin >> T;
    while (T--) {
        int n, k;
        cin >> n >> k;

        vector <int> b(n);
        vector <int> c(n);
        for (int i = 0; i < n; i++) {
            cin >> b[i];
        }
        for (int i = 0; i < n; i++) {
            cin >> c[i];
        }

        int bound = 0;
        for (int i = 0; i < n; i++) {
            bound += d[b[i]];
        }

        bound = min(bound, k);
        vector <int> dp(bound + 1);
        for (int i = 0; i < n; i++) {
            int x = d[b[i]];
            for (int j = bound; j >= x; j--) {
                dp[j] = max(dp[j], dp[j - x] + c[i]);
            }
        }

        cout << *max_element(dp.begin(), dp.end()) << endl;
    }
}