农夫约翰想用他的 B 个货币单位的总预算给他的 N 头奶牛送礼物。 奶牛 i 希望得到价格为 P(i) 个单位的礼物，运费为 S(i) 个单位（因此农夫订购此礼物的总成本为 P(i)+S(i)）。 农夫有一张特别优惠券，他可以用它以正常价格的一半价格订购一件他选择的礼物。 如果农夫使用奶牛 i 的优惠券，那么他只需要为奶牛的礼物支付 P(i)/2+S(i)。 请帮助农夫确定他最多可以给多少头牛送礼物。
输入格式
第一行为两个正整数 N 和 B 。(1 <= B <= 1,000,000,000，1 <= N <= 1000) 接下来 N 行，每行为两个正整数 P(i) 和 S(i) 。 0 <= P(i),S(i) <= 1,000,000,000，P(i) 均为偶数。