题目描述

有 $N$ 种物品和一个容量为 $V$ 的背包。第 $i$ 种物品的体积是 $C_i$ ，得到的价值是 $W_i$。求解将哪些物品装入背包可使价值总和最大,每种物品有无数件。

输入格式

第一行是两个整数 $N$ 和 $V$（$1 \le N,V \le 1000$）。

接下来 $N$ 行，每行有两个数 $C_i$ 和 $W_i$（$1 \le C_i,W_i \le 1000$），分别代表体积和价值。

输出格式

输出能得到的最大价值。

样例

5 10
1 5
2 4
3 3
4 2
5 1

50