问题描述

有 N 件物品和一个容量为 V 的背包。放入第 i 件物品耗费的空间是 vi，得到的价值是 wi。求解在背包恰好装满的情况下，将哪些物品装入背包可使价值总和最大。

输入格式

第 1 行两个正整数，分别表示物品数量 N 和背包容量 V，中间用一个空格隔开。

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

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

其中：$1\le N\le 100，1\le V\le 10^6 ，1\le vi,wi\le 10000$。

输出格式

一行，一个正整数，表示背包恰好装满的情况下最大的价值总和。

如果无论怎么选择物品，背包都没办法恰好塞满，则输出取得最大价值时放入背包的物品的总体积。

样例输入1

4 16
8 9 5 2
5 6 7 3

样例输出1

16

样例说明1

本例中，选择体积为9、5、2的物品，是所有“正好塞满背包的方案”中取得最大价值总和的方案，所以输出该方案的价值16（=6+7+3）。

样例输入2

4 20
8 9 5 2
5 6 7 3

样例输出2

16

样例说明2

本例中，无论怎么选择物品，都无法正好塞满体积为20的背包，所以输出取得最大价值时的物品总体积16（=9+5+2）。