Bounded Knapsack

// https://szkopul.edu.pl/problemset/problem/klvaggzD-q4Acz_WLtkn0JXJ/site/?key=statement
#include <bits/stdc++.h>
#define index first
#define cost second

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int N;
    cin >> N;
    vector < int > b(N + 1);
    for(int i = 1; i <= N; ++i)
        cin >> b[i];
    vector < pair < int , int > > a(4096);
    int M = 0;
    for(int i = 1; i <= N; ++i) {
        int x;
        cin >> x;
        int val = 1;
        while(x) { // log2 trick
            if(x >= val) {
                a[++M] = make_pair(i, val);
                x -= val;
            }
            else {
                a[++M] = make_pair(i, x);
                x = 0;
            }
            val <<= 1;
        }
    }
    int K;
    cin >> K;
    bitset < 20001 > mark;
    mark.set(0);
    vector < int > dp(K + 1), dim(K + 1);
    vector < vector < short > > parts(K + 2, vector < short >(1001));
    for(int i = 1; i <= M; ++i) {
        int val = b[a[i].index] * a[i].cost;
        for(int j = K; j >= val; --j)
            if(mark.test(j - val))
                if(!mark[j] || dp[j - val] + a[i].cost < dp[j]) {
                    mark.set(j);
                    dp[j] = dp[j - val] + a[i].cost;
                    for(int x = 1; x <= dim[j - val]; ++x)
                        parts[j][x] = parts[j - val][x];
                    parts[j][dim[j - val] + 1] = i;
                    dim[j] = dim[j - val] + 1;
                }
    }
    cout << dp[K] << '\n';
    vector < int > sol(N + 1);
    for(int i = 1; i <= dim[K]; ++i)
        sol[a[parts[K][i]].index] += a[parts[K][i]].cost;
    for(int i = 1; i <= N; ++i)
        cout << sol[i] << ' ';
}