学校发暑期福利啦，给了你总共能容纳V大小的背包，允许你到超市里任意选购商品，学校报销哦。

现在超市有3类物品。第一类物品每种有无数件，共n种。第二类物品每种有1件，共m种。第三类物品每种有ai件，共k种。

每种物品有其大小bi，与价值vi。现需要你计算出你能得到的最大价值是多少？

输入输出格式
输入格式
第一行包含4个整数n,m,k,V。
第二行包含n+m+k个整数，表示bi。按第一类、第二类、第三类顺序给出。
第三行包含n+m+k个整数，表示vi。按第一类、第二类、第三类顺序给出。
第四行包含k个整数，表示ai。
输出格式
一个整数，表示最大价值。
输入输出样例
输入样例#1:
1 2 2 10364
474 129 389 18 244 
124 302 47 376 116 
8939 22209 
输出样例#1:
216200

#include <iostream>
#include <cstring>
using namespace std;

const int N = 10141430;

int n, m, k;
int v[N], w[N], s[N];
int f[N];

int main()
{
    int V;
    cin >> n >> m >> k >> V;
    for (int i = 0; i < n + m + k; i ++ )
        cin >> w[i];
    for (int i = 0; i < n + m + k; i ++ )
        cin >> v[i];
    for (int i = n + m; i < n + m + k; i ++ )
        cin >> s[i];

    memset(f, 0, sizeof f);
    for (int i = 0; i < n + m; i ++ )
        for (int j = V; j >= w[i]; j -- )
            f[j] = max(f[j], f[j - w[i]] + v[i]);

    for (int i = n + m; i < n + m + k; i ++ )
    {
        if (s[i])
        {
            int tot = 1;
            while (tot < s[i])
            {
                for (int j = V; j >= tot * w[i]; j -- )
                    f[j] = max(f[j], f[j - tot * w[i]] + tot * v[i]);
                s[i] -= tot;
                tot <<= 1;
            }
            for (int j = V; j >= s[i] * w[i]; j -- )
                f[j] = max(f[j], f[j - s[i] * w[i]] + s[i] * v[i]);
        }
    }

    cout << f[V] << endl;

    return 0;
}

40分

input

77 1 54 190936
171 69 413 154 134 98 144 310 27 255 85 438 394 344 462 151 379 448 303 485 250 37 470 251 387 390 26 303 62 431 342 63 356 251 94 53 218 263 453 346 286 326 244 473 372 263 348 316 87 280 4 315 455 292 350 226 229 372 377 254 129 240 16 403 405 221 261 259 429 326 22 269 459 161 241 297 226 176 304 129 87 276 105 71 263 422 217 488 49 57 323 479 339 87 345 288 268 354 398 264 101 243 47 422 253 471 390 96 4 97 256 354 434 447 444 187 184 145 439 446 19 22 199 388 317 165 260 383 414 133 176 95
248 175 190 415 7 428 46 14 481 488 432 209 407 413 338 8 120 479 216 448 266 158 263 256 334 213 421 260 415 49 351 390 197 97 337 369 405 473 164 167 115 41 83 257 254 125 291 306 442 116 232 228 496 83 167 312 7 120 251 166 364 192 320 229 200 336 208 95 492 423 413 263 330 173 426 399 346 380 448 183 476 56 210 316 449 261 350 420 358 70 338 207 286 60 128 278 274 435 397 415 374 401 415 418 60 34 288 77 57 371 326 285 260 60 377 338 41 415 329 84 282 114 320 255 197 60 441 54 487 259 165 31
38322 18266 32142 18950 13126 17197 1824 12834 15139 3385 21104 4506 268 36472 14460 4989 17982 8504 38638 27025 18030 22756 21718 26682 12983 22252 6440 4870 8284 8779 9174 33045 27360 9870 21242 5388 33930 11776 15418 9167 31781 19571 18189 20257 26559 34814 97 22663 4705 32823 33956 6538 19707 39454
output

11074288
myOutput

2834335