题目背景

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 提供解法。