农夫约翰想给他的 N 头奶牛购买礼物，但是他的预算只有 B 元。

奶牛 i 希望获得的礼物的价格为 Pi，运输成本为 Si，也就是说约翰要帮奶牛 i 买礼物，共需花费 Pi+Si 元钱。

约翰有一张特殊的优惠券，如果使用该优惠券来订购一份礼物，那么该礼物的价格会变为只有正常价格的一半。

如果约翰用该优惠券给奶牛 i 买礼物，那么他只需要支付 Pi/2+Si 元钱。

方便起见，Pi 一定是偶数。

请帮助约翰确定他最多可以给多少头奶牛购买礼物。

输入格式
第一行包含两个整数 N 和 B。

接下来 N 行，每行包含两个整数 Pi 和 Si。

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

数据范围

1≤N≤1000,
1≤B≤10⁹,
0≤Pi,Si≤10⁹

输入样例：

输出样例：

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

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

题目分析

对于每一件物品有一个价格和一个运输价格，我们有且只有一张优惠券，而优惠券仅可对原价格进行半价优惠，我们要就算在预算范围内，最多可以购买多少个礼物
误区：直接进行排序，优先选择最低价格的礼物，同时判断对超出预算的第一个礼物进行优惠处理是否可以继续购买
样例
2 170
10 100
20 50
正解：由于数据范围只有 1000 直接进行暴力枚举即可，枚举对每一个礼物进行优惠，所能购买的最大数量
时间复杂度：O(10⁶)