题目描述

一次，jyz 的电脑又坏了，他决定修一修。

不过，他吃了上一次的堑，他决定，事先备份一些文件。

每个文件都有备份的时间 $t_i$，文件大小 $m_i\text{KB}$。而 jyz 只能存 $x\text{MB}$ 的文件。于是他希望你告诉他在最多能存多少份文件的前提下，时间最短是多少。

输入格式

第一行为一个整数 $n,x$，表示有 $n$ 个文件和 jyz 最多可以存 $x\text{MB}$ 的文件。

接下来 $n$ 行，每行两个整数 $t_i$ 和 $m_i$，意义见上。

输出格式

一个整数，表示在最多能存多少份文件的前提下，时间最短是多少。

样例

5 1
3 12
5 100
9 1000
8 24
4 912

12

样例解释

最多存 $3$ 份，且选择第 $1,2,5$ 份文件即可使时间最短。

数据范围

对于 $100\%$ 的数据，$1 \le n,x \le 30,1 \le t_i,m_i \le 5 \times 10^6$。