题目描述

元旦要到了，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

10 280
18 30
20 37
18 47
10 35
22 36
16 32
10 38
12 32
18 36
12 36

6

说明

样例1解释

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

数据规模

对于 50% 的数据，满足 $1≤n≤100$。

对于 100% 的数据，满足 $1≤n≤1000, 1≤s≤10^9*,1≤s≤10^9，0≤*ai,bi≤10^9$ 。