问题描述

小明有一个容量为 V 的背包，和 N 种物品（每种物品有无限个）。第 i 种物品的体积是 v[i]，价值是 w[i]。 请计算在背包容量允许的情况下，能装入物品的最大总价值是多少？

格式

输入

• 第一行包含两个整数 N 和 V，分别表示物品种数和背包容量。
• 接下来 N 行，每行两个整数 v[i] 和 w[i]，表示第 i 种物品的体积和价值。

输出

• 输出一个整数，表示最大总价值。

样例

3 5
1 2
2 4
3 4

10

提示

• 1 ≤ N ≤ 1000
• 1 ≤ V ≤ 10000
• 1 ≤ v[i], w[i] ≤ 10000