Responsive image

问题 B: 礼物

问题 B: 礼物

时间限制: 1 Sec  内存限制: 128 MB
提交: 0  解决: 41
[提交][状态][讨论版][命题人:]

题目描述

农夫约翰想给他的 N 头奶牛购买礼物，但是他的预算只有 B 元。
奶牛 i 希望获得的礼物的价格为 Pi，运输成本为 Si，也就是说约翰要帮奶牛 i 买礼物，共需花费 Pi+Si 元钱。
约翰有一张特殊的优惠券，如果使用该优惠券来订购一份礼物，那么该礼物的价格会变为只有正常价格的一半。
如果约翰用该优惠券给奶牛 i 买礼物，那么他只需要支付 ⌊Pi/2⌋+Si 元钱。
请帮助约翰确定他最多可以给多少头奶牛购买礼物。


输入描述

第一行包含两个整数 N 和 B。
接下来 N 行，每行包含两个整数 Pi 和 Si。
1≤N≤1000,
1≤B≤109,
0≤Pi,Si≤109

输出描述

输出约翰可以购买礼物的奶牛最大数量。

样例输入

5 24
4 2
2 0
8 1
6 3
12 5

样例输出

4

提示

一种最佳方案是约翰给前 4 头奶牛购买礼物，在给第 3 头奶牛购买礼物时使用优惠券。



花费为 (4+2)+(2+0)+(4+1)+(6+3)=22。

[提交][状态]
ACM算法攻关部