又见完全背包

题目描述

有n种物品，第i种物品的重量和价格为w_i、v_i。每种物品数量无限。背包最大载重量为C。今要把背包装满，并使得背包内物品价值之和最大。

输入

第一行两个正整数n和C。

第二行为n个正整数w_i, i=1,2,...,n。

第三行为n个正整数v_i, i=1,2,...,n。

输出

背包所能容纳物品的最大价值。

样例

提示

对于100%的数据，有1≤N≤100，1≤C≤10^{12},C/100≤w_i≤10^{12}，1≤v_i≤1000。

来源

原创