#P1015. 认真学习的一天(但是拒绝内卷)

认真学习的一天(但是拒绝内卷)

说明

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

今天是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

提示

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