描述

Cindy为了庆祝自己的生日，决定去商店给自己买一些礼物。

假设有商店里有\(N\)件礼物，每件礼物的价格为\(w_i\)元，价值为\(v_i\)，Cindy只带了\(V\)元钱，每种礼物可以买任意自然数件。请你计算出Cindy买下的礼物所能获得的最大价值和。

格式

输入格式

第一行为两个数，\(N\)和\(V\)。
接下来的\(N\)行，每行两个数，第\(i+1\)行的两个数分别为\(w_i\)和\(v_i\)。

\(1\leq N,V\leq 1000\)
\(1\leq w_i,v_i\leq 1000\)

输出格式

一行，所能获得的最大价值和。

样例

输入样例

4 5
1 2
2 4
3 4
4 5

输出样例

10

限制

内存256MB，时间1s。