1371 - 0-1背包问题

通过次数

3

提交次数

64

Time Limit : 1 秒
Memory Limit : 64 MB

有n件物品,每件物品有一个重量和一个价值,分别记为W1,W2,…,Wn和C1,C2,…,Cn。

现在有一个背包,其容量为Wk,要从n件物品中任取若干件,要求:

(1)重量之和小于或等于Wk。

(2)价值之和最大。

Input

15654207175070.png

Output

一个正整数,表示最大价值。

Examples

Input

8 20
79 58 86 11 28 62 15 68
83 14 54 79 72 52 48 62

Output

334

Source

课课通