题目描述

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

他列出了采购清单：

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

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

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

输入格式

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

第 2...n+1 行，每行两个整数，分别表示 ai​ 和 bi​ 。

输出格式

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

5 24
4 2
2 0
8 1
6 3
12 5

4