2010 - 0-1背包问题-1

通过次数

177

提交次数

602

Time Limit : 1 秒
Memory Limit : 64 MB

有N件物品和一个容量为C的背包。放入第i件物品耗费的空间是w_i,得到的价值是v_i。求解在不超过容量的前提下,将哪些物品装入背包可使价值总和最大。

Input

第1行两个正整数,分别表示N和C,中间用一个空格隔开。

第2行N个正整数,表示w_i,中间用一个空格隔开。

第3行N个正整数,表示v_i,中间用一个空格隔开。

其中:1≤N≤100,1≤C≤10^6 ,1≤w_i≤10000,1≤v_i≤10000。

Output

一行一个正整数,表示最大的价值总和。

Examples

Input

4 20
8 9 5 2
5 6 7 3

Output

16

Source

动规专题