问题说明

由于期末考考的很好，妈妈给小明买了一台游戏机，但是游戏机的容量有限，只能安装部分游戏。小明玩每种游戏的开心程度是不一样的，并且每种游戏需要的容量也不同。小明安装完游戏后，玩了一段时间游戏，又发现一个问题，就是游戏机容量还是有一点点的浪费，他现在又有一个新的主意，就是把游戏刚好装满游戏机，让游戏机的剩余容量为零，这样他觉得就不浪费了。请帮助小明选择合理的游戏，让小明的开心程度的总和最大。注意小明不是傻子，同一种游戏不会装两个。

输入格式

第1行，两个整数n和m，分别表示游戏的个数和游戏机的容量 (1<=n<=30，1<=m<=100)

第2行到最后，每行两个整数wi和vi，分别表示这种游戏需要的容量和小明玩这种游戏的开心程度（1<=wi<=500，1<=vi<=500）

输出格式

一个整数，为小明的开心程度总和的最大值。如果游戏怎么装实现不了刚好装满的情况，则输出-1

4 15
2 1
3 3
4 5
7 9

-1

提示

样例输入2
4 14
2 1
3 3
4 5
7 9

样例输出2
17

来源/分类