题目描述

小瓜是举世闻名的魔女，她凭一己之力就可以构筑一整座魔法城堡。建造城堡要消耗魔法药水，她可以任意搭配这些药水的比例，但是使用不同的药水要耗费不同程度的法力值。小瓜收藏了 $n$ 种魔法药水，第 $i$ 种魔法药水每瓶需要耗费 $a_i$ 点法力值，该种药水的数量为 $b_i$ 瓶。每瓶药水会为最终的城堡贡献 $1$ 点豪华程度。小瓜当前拥有 $m$ 点法力值，她想在有限的法力值之内建造一个豪华程度尽可能高的城堡，请你求出能够达到的最大豪华程度是多少。

输入格式

第一行：输入两个整数 $n,m$，分别表示魔法药水的种类数，以及小瓜的法力值上限。

此后 $n$ 行：每行输入两个整数 $a_i,b_i$，表示第 $i$ 种魔法药水每瓶消耗的法力值和数量。

输出格式

输出一个整数，表示城堡豪华程度的最大值。

样例

5 50
5 3
1 1
10 4
7 2
60 1

8

样例 $1$ 解释

将第 $1,2,4$ 种魔法药水全部用完，第 $3$ 种魔法药水用 $2$ 瓶，总共消耗的法力值为 $50$，总豪华程度为 $8$。

数据范围

对于 $30\%$ 的测试点，满足 $1≤n≤1000,1≤m≤10^9，1≤a_i,b_i≤10^9$。

对于 $100\%$ 的测试点，满足 $1≤n≤10^5,1≤m≤10^9，1≤a_i,b_i≤10^{18}$。