P6721: 新年礼物（gifts）
传统题
1.000s
时间限制
128MB
内存限制
1 提交
0 解决
【题目描述】
【题目背景】
过新年了，黄老师想给同学们买一些礼物寄给大家。
【题目描述】
因为今年NOIP比赛大家成绩都很好，为了奖励大家，在新年的时候黄老师想要从网上买一些礼物寄给大家。黄老师调研了大家喜欢的礼物，并且一一上网查到了商品的价格，统计出了一张表。
黄老师有n名学生，每名学生想要的礼物都有一个价格pi和邮费si，也就是说，购买这件礼物需要付pi+si元。黄老师只有b元的预算，他想给尽量多的同学购买礼 物。黄老师在整理购物车的时候发现，tb也给了他一个新年礼物，那就是一张优惠券。这张优惠券能够让一个商品以半价购买，既使用了优惠券的商品需要付 pi/2+si元。
【输入格式】
从文件 gifts.in
中读入数据。
第1行有2个正整数，表示共有n名学生和b元钱。
第2到n+1行，每行有两个正整数，分别代表这名同学想要的礼物的价格pi和邮
费si，数据保证pi一定为偶数。
【输出格式】
输出到文件 gifts.out
中。
输出一行一个整数，表示要黄老师能够购买的最多礼物数。
【样例 1 输入】
5 24
4 2
2 0
8 1
6 3
12 5
【样例 1 输出】
4
【样例 1 解释】
共有5名学生，有24元的预算。如果给第1~4名同学购买礼物，并且在购买第三
名同学的礼物时使用优惠券的话，总共会花(4+2)+(2+0)+(4+1)+(6+3) = 22
元，满足预算。容易发现黄老师无法给全部5名同学都买礼物，因此答案为4。
需要注意的是，在给1~4名同学买礼物时，这张优惠券如果在第1名同学或第4名
同学的礼物上使用，也可以满足预算条件。
【样例 2】
见选手目录下的gifts / gifts 2.in
与 gifts / gifts 2.ans
。
【样例 3】
见选手目录下的 gifts / gifts 3.in
与 gifts / gifts 3.an
s。
【数据范围】
对于20%的数据，1 ≤ n ≤ 10，1 ≤ b，pi，si ≤ 1000；
对于60%的数据，1 ≤ n ≤ 5000，1 ≤ b，pi，si ≤ 10^9；
对于100%的数据，1 ≤ n ≤ 200000，1 ≤ b，pi，si ≤ 10^9。