题目描述

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

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

$$\boxed{ \begin{matrix} \text{巧克力品种}&\text{单价}&\text{高兴的奶牛数量}\\ 1&5&3\\ 2&1&1\\ 3&10&4\\ 4&7&2\\ 5&60&1 \end{matrix} } $$

显然约翰不会去买第 $5$ 种巧克力，因为他钱不够，不过即使它降价到 $50$，也不该选择它，因为这样只会让一头奶牛高兴，实在太浪费了。最好的买法是：第 $2$ 种买 $1$ 块，第 $1$ 种买 $3$ 块，第 $4$ 种买 $2$ 块，第 $3$ 种买 $2$ 块，正好用完 $50$ 元，可以让 $1+3+2+2=8$ 头牛高兴。

输入格式

第一行：两个用空格分开的整数：$n, b$。

第二行到 $n+1$ 行：第 $i+l$ 行，是两个用空格分开的整数：$p_j$ 和 $c_i$。

输出格式

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

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

8

数据规模与约定

对于 $100\%$ 的数据，$1 \leq n \leq 1\times10^5$，$1 \leq b \leq 10^{18}$ 且 $1 \leq p_i, c_i \leq 10^{18}$。

题目来源

Silver