农夫约翰想给他的 N 头奶牛购买礼物，但是他的预算只有 B 元。
奶牛 i 希望获得的礼物的价格为 Pi，运输成本为 Si，也就是说约翰要帮奶牛 i 买礼物，共需花费 Pi+Si 元钱。
约翰有一张特殊的优惠券，如果使用该优惠券来订购一份礼物，那么该礼物的价格会变为只有正常价格的一半。
如果约翰用该优惠券给奶牛 i 买礼物，那么他只需要支付 ⌊Pi/2⌋+Si 元钱。
请帮助约翰确定他最多可以给多少头奶牛购买礼物。
2569: 礼物
时间限制: 1 Sec 内存限制: 128 MB提交: 0 解决: 41
[提交][状态][讨论版][命题人:]
题目描述
输入描述
第一行包含两个整数 N 和 B。
接下来 N 行，每行包含两个整数 Pi 和 Si。
1≤N≤1000,
1≤B≤109,
0≤Pi,Si≤109
接下来 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。
来源
-
Anything about this OnlineJudge, Please Contact Administrator. Click add QQ
OJ system based on HUSTOJ Project , UI based on Twitter Bootstrap
Copyright 2016 ACM算法攻关部
关于网站改版