问题描述

K哥是100122号游戏高手，他最近在玩很多游戏，但是遇到了一些烦人的问题，于是他找到了你，需要你帮他解决。

K哥迷恋的游戏太多了，比如说：三国杀，魔兽，武林英雄……再加上K哥也是人，他也有梦想，也要学习，还要搞信息，还要泡MM，所以他并没有多少时间玩游戏，所以他需要合理规划。

K哥正在玩的游戏有N种，他每天可以玩无限次游戏，但玩游戏是要消耗时间的，每玩一个游戏一次需要花费Ki秒钟的时间，可以使K哥获得Vi点兴奋度，但K哥每天玩游戏的时间不能超过m小时，请你计算出K哥一天最多能获得多少点兴奋度。

输入格式

共N+1行

第一行：N,m(1<=N<=1000，1<=m<=10)

第2~N+1行：每行两个数Ki,Vi,含义如题所示。

输出：

共1行

第一行：一个整数ans,表示K哥一天最多能获得的兴奋点数。

样例：kbs.in

5 1
3601 5000
3000 5
2096 3
2601 2000
5000 1995

kbs.out

2000