元旦要到了，XH 决定给他天南地北的 N 个朋友每人送上一份礼物，他一共准备了 S 元礼物基金。

他列出了采购清单：

为第 i 位朋友购买的礼物需要 a_i 元，且还需要 b_i 元快递费。

正逢百货大楼做元旦活动，XH 抽中一张奖券，可以半价购买一件商品，（如果这张奖券用于购买第 i 件礼物，对于这件礼物的总开销为 a_i / 2 + b_i 元，保证 a_i 为偶数）。

XH想知道他最多可以购买多少件礼物，请你帮他算一算。

第一行，两个整数，分别是 N 和 S 。

第 2...n+1 行，每行两个整数，分别表示 a_i 和 b_i 。

一个整数，表示 XH 最多能给几个朋友送礼物。

样例 1 解释

购买 1 到 4 的礼物，奖券给 3 使用，(4+2)+(2+0)+(4+1)+(6+3) = 22 ，他也可以将优惠券使用在 1 或者 4 。

数据规模

对于 50\% 的数据，满足 1 \le N \le 100。

对于 100\% 的数据，满足 1 \leq N \leq 1000 ， 1 \leq S \leq 10^9， 0 \leq a_i , b_i \leq 10^9 。

东方博宜OJ

月赛结构体贪心2024