题目描述

这天，zj 睡着了之后，做了一个梦。只见他背着一个包，容量为 $V$，路经一座岛，岛上有 $N$ 种奇怪的珠宝，每种珠宝有无限多件。其中每件珠宝的体积为 $v_i$ ，价值为 $w_i$。zj 醒来之后，不知道怎么装珠宝，才能仅凭这一个背包装下最大价值的珠宝。他想到了聪明的你，请你编程帮他解决。

输入格式

第一行两个整数，$N,V$（$0\lt N,V \le 1000$），用空格隔开，分别表示物品种数和背包体积。

接下来有 $N$ 行，每行两个整数 $v_i, w_i$（$0 < v_i,w_i\le 1000$），用空格隔开， 分别表示第 $i$ 种物品的体积和价值。

输出格式

输出一行一个整数表示最大价值。

输入样例

4 5
1 2
2 4
3 4
4 5

输出样例

10