P2707 Facer Helps His Father

Facer is a very filial child.

Facer's father is a manager and is now always dejected. Facer asked his father, what's wrong? His father said, the company has a problem. The company manages $n$ scenic spots, each of which has many visitors. But now, people complain that the ticket prices are too high, so he has to adjust the prices. Specifically, for the $i$-th scenic spot, if the ticket price is $x$, the number of visitors is $\max( (a_i - b_i\times x),0 )$. You need to assign the ticket price for each scenic spot such that the sum of ticket prices over all scenic spots does not exceed $k$, and find the maximum revenue.

The first line contains two integers $n, k$. Then follow $n$ lines, each containing two integers $a_i, b_i$.

One line, indicating the maximum revenue.

Sample explanation: Scenic spot $1$ ticket price is $3$, scenic spot $2$ ticket price is $1$. Scenic spot $1$ visitors: $50 - 3\times 2 = 44$, revenue: $132$. Scenic spot $2$ visitors: $40 - 1\times 1 = 39$, revenue: $39$. The total revenue is $171$. - For $10\%$ of the testdata, $1 \le n \le 5$, $1 \le k \le 5$. - For $30\%$ of the testdata, $1 \le n \le 100$, $1 \le k \le 100$. - For $60\%$ of the testdata, $1 \le n \le 2000$, $1 \le k \le 2000$. - For $100\%$ of the testdata, $1 \le n \le 100000$, $1 \le k \le 100000$, $1 \le a_i, b_i \le 100000$. Thanks to zhouyonglong for providing the solution. Translated by ChatGPT 5