题目描述

小明有 $S$ 元钱，商店中有 $N$ 件商品。第 $i$ 件商品的价格为 $a_i$ 元，快递费为 $b_i$ 元。购买一件商品需要支付商品价格和快递费。

小明可以选择其中至多一件商品，使这件商品的价格减半，快递费不变。价格减半后取整数部分。例如，价格为 $9$ 元时，减半后为 $4$ 元。

在总花费不超过 $S$ 元的情况下，请计算小明最多可以买多少件商品。每件商品最多购买一次。

输入格式

第一行包含两个整数 $N,S$，分别表示商品数量和小明拥有的钱数。

接下来 $N$ 行，每行包含两个整数 $a_i,b_i$，分别表示第 $i$ 件商品的价格和快递费。

输出格式

输出一个整数，表示最多可以买到的商品数量。

4 17
9 1
8 4
7 0
20 0

2

数据范围与提示

• $1 \le N \le 1000$
• $0 \le S \le 10^9$
• $1 \le a_i \le 10^9$
• $0 \le b_i \le 10^9$