#O1035. 完全背包

完全背包

题目描述

有 nn 种物品,第 ii 种重 wiw_i、价值 viv_i,每种物品可以取任意多件,背包容量为 WW,求最大总价值。

题目类型

动态规划、完全背包

输入格式

第一行两个整数 n,Wn, W。

第二行 nn 个整数 wiw_i。

第三行 nn 个整数 viv_i。

输出格式

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

样例 #1

样例输入 #1

2 5
1 3
2 5

样例输出 #1

10

数据规模与约定

数据范围 说明
1≤n≤5001 \le n \le 500 物品种数
0≤W≤5×1040 \le W \le 5 \times 10^4 背包容量
1≤wi≤1091 \le w_i \le 10^9 重量
1≤vi≤1061 \le v_i \le 10^6 价值