农夫约翰想给他的 N 头奶牛购买礼物，但是他的预算只有 B 元。
奶牛 i 希望获得的礼物的价格为 Pi，运输成本为 Si，也就是说约翰要帮奶牛 i 买礼物，共需花费 Pi+Si 元钱。
约翰有一张特殊的优惠券，如果使用该优惠券来订购一份礼物，那么该礼物的价格会变为只有正常价格的一半。
如果约翰用该优惠券给奶牛 i 买礼物，那么他只需要支付 ⌊Pi/2⌋+Si 元钱。
请帮助约翰确定他最多可以给多少头奶牛购买礼物。
第一行包含两个整数 N 和 B。
接下来 N 行，每行包含两个整数 Pi 和 Si。
输出约翰可以购买礼物的奶牛最大数量。
5 24
4 2
2 0
8 1
6 3
12 54
1≤N≤1000,
1≤B≤109,
0≤Pi,Si≤109
样例解释
一种最佳方案是约翰给前 4 头奶牛购买礼物，在给第 3 头奶牛购买礼物时使用优惠券。