题目描述

有N件物品和一个容量为V的背包。放入第i件物品占据的空间是wi，价值是ci，求将哪些物品放入背包，在不超过容量的情况下，可使这些物品的价值最大。

输入格式

第1行两个正整数N(1≤N≤100)和V(1≤V≤1000)；

第2行N个正整数，表示wi(1≤wi≤100)；

第3行N个正整数，表示ci(1≤ci≤100)。

输出格式

一个整数，表示最大的价值总和。

输入/输出样例

4 20
8 9 5 2
5 6 7 3

16

说明/提示

时间1000ms，内存256MiB