说明

咳咳，既然是每个人都出一道题，那我就出一道简单题吧......

今天是night学习背包算法的第一天，night信心昂扬，迫不及待地打开了学习文件，然后.......发现基本看不懂，傻眼了，

于是night匆匆打开某个学习网站准备从零开始学习，幸运的是，他发现了许多有价值的学习视频，night仔细看了看，

共有m种不同的视频，每个视频都有其自身的经验v和内容量w，而且如果一遍没看懂还可以反复观看， 但每看一遍视频

都会消耗night的脑力，重新燃起斗志的night惊奇的发现他获得了一个神奇的BUFF——当他力竭（脑力消耗完）之时，他的

脑力会完全恢复并且学习效率也会大幅提升，也就是说在他获得BUFF后每学习一个视频能获得双倍的经验且只消耗一半的脑力(数据取整)，

已知night的脑容量是n，已经一心投入学习无暇顾及其他的night想请你帮他算算，他今天最多能获得多少经验呢？

输入格式

第一行输入m，n，代表有m种视频，night的脑容量为n。

第2行到第m+1行，输入视频的经验v和内容量w。

m<=10, 2<=n,v,w<=10^4。

输出格式

一行输出night所能获得的最大经验。

样例

3 7 
4 3
6 2
8 3

132

提示

完全背包变.....这都算不上变形吧？算了，我坦白，就是完全背包模板。