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

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

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

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

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

第一行包含两个整数 N 和 B。

接下来 N 行，每行包含两个整数 P_i 和 S_i。

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

1 ≤ N ≤ 1000，1 ≤ B ≤ 10^9，0 ≤ P_i, S_i ≤ 10^9。