Start: Apr, 12, 2024 15:00:00
20240412动态规划复习
End: May, 12, 2024 19:00:00
Time elapsed:
Time remaining:

(L3-12)实现完全背包 1854

Time Limit:  1 Sec    Memory Limit:   128 MB
Submission:11     AC:8     Score:100


Description

给定 $N$ 种物品和一个背包,每种物品有无限多个,物品 $i$ 的价值是 $W_i$,其体积为 $C_i$,背包的容量为 $C$。

问应该如何选择装入背包的物品,使得装入背包的物品的总价值为最大。

Input

第一行两个整数 $N$,$V(N \leq 100, V \leq 20000)$ 表示物品数量和背包大小

接下来 $N$ 行,每行两个整数分别表示第 $i$ 个物品的体积 $c[i]$ 和 价值 $w[i]$

Output

输出能装走物品的最大价值

Samples

input:
3 10 4 5 3 4 6 9
output:
14