Problem D: 游戏快乐值

Memory Limit：128 MB Time Limit：1.000 S
Judge Style：Text Compare Creator：
Submit：14 Solved：9

Description

新春嘉年华游乐场的扭蛋机卖 n 种游戏卡，第 i 种每张价格 ci 元、能玩出快乐值 vi， 每种想买几张买几张（无限次）。

妈妈给小明 m 元钱，小明想把快乐值拉满：花的钱不超过 m，能获得的最大快乐值是多少？

例如: 有2种游戏卡，小明有8元钱。3元的游戏卡能玩出快乐值4 ，2元的游戏卡能玩出快乐值3。

        答案为: 小明用 8 元的买法：
                    • 2 元卡买 4 张：快乐值 3×4 = 12 

                    • 若买二张3元卡及一张2元卡;快乐值 4+4+3=11 更低

                    所以最大快乐值是 12。注意"2 元卡能买 4 张"——这正是和 0/1 背包的本质区别！


Input

第一行：n m
接下来 n 行，每行两个整数 ci 与 vi（价格、快乐值）

Output

一个整数：最大快乐值

Sample Input Copy 

2 8
3 4
2 3

Sample Output Copy 

12

HINT

1<n<=100;  1<n<=10000;  1=<ci与vi<=1000。