题目描述

贝西和其他奶牛们都喜欢巧克力，所以约翰准备买一些送给她们。奶牛巧克力专卖店里 有$\red{N}$种巧克力，每种巧克力的数量都是无限多的。每头奶牛只喜欢一种巧克力，调查显示， 有$\red{Ci}$头奶牛喜欢第$\red{i}$种巧克力，这种巧克力的售价是$\red{P}$。

约翰手上有$\red{B}$元预算，怎样用这些钱让尽量多的奶牛高兴呢？下面举个例子：假设约翰有$\red{50}$元钱，商店里有$\red{S}$种巧克力：

显然约翰不会去买第五种巧克力，因为他钱不够，不过即使它降价到$\red{50，}$也不该选择

它，因为这样只会让一头奶牛高兴，实在太浪费了。最好的买法是：第二种买$\red{1}$块，第一种 买$\red{3}$块，第四种买$\red{2}$块，第三种买$\red{2}$块，正好用完$\red{50}$元，可以让$\red{1+3+2+2=8}$头牛高兴。

输入格式

第一行：两个用空格分开的整数：$\red{N}$和$\red{B，}$$\red{1<=N≤}$$\red{100000，}$$\red{1≤}$$\red{B≤}$$\red{10^{18}}$

第二行到$\red{N+1}$行：第$\red{i+l}$行，是两个用空格分开的整数：$\red{Pj}$和$\red{Ci，}$$\red{1≤}$$\red{Pi，}$$\red{Ci≤}$$\red{10^{18}}$

输出格式

第一行：一个整数，表示最多可以让几头奶牛高兴

样例

输入样例

5 50
53
11
10 4
7 2
60 1

输出样例

8