Facer 帮父亲

Facer 可是一个孝顺的孩纸呦

Facer 的父亲是一名经理，现在总是垂头丧气的。 Facer 问父亲，怎么啦？父亲说，公司出了点问题啊。 公司管理着 $n$ 个风景点，每个风景点都有不少人来参观。 可是现在！人民投诉票价太高了，他不得不调整票价。 具体来说，第 $i$ 个景点如果票价是 $x$，来的人数就是 $\max( (a_i - b_i\times x),0 )$。 你需要分配每个景点的门票，使得所有景点的门票总价之和不超过 $k$，求最大的收益。

第一行两个整数 $n, k$。 接下来 $n$ 行，每行两个整数 $a_i,b_i$。

一行，表示最大的收益。

2 4
50 2
40 1

171

样例解释： 景点 $1$ 票价 $3$，景点 $2$ 票价 $1$。 景点 $1$ 人数：$50 - 3\times 2 = 44$，收益：$132$。 景点 $2$ 人数：$40 - 1\times 1 = 39$，收益：$39$。 总收益为 $171$。 - 对于 $10\%$ 的数据，$ 1 \le n \le 5 , 1 \le k \le 5$； - 对于 $30\%$ 的数据，$ 1 \le n \le 100, 1 \le k \le 100$； - 对于 $60\%$ 的数据，$ 1 \le n \le 2000, 1 \le k \le 2000$； - 对于 $100\%$ 的数据，$ 1 \le n \le 100000, 1 \le k \le 100000,1 \le a_i , b_i \le 100000$。 鸣谢 zhouyonglong 提供解法。