Description

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.

Input Format

The first line contains two integers $n, k$.

Then follow $n$ lines, each containing two integers $a_i, b_i$.

Output Format

One line, indicating the maximum revenue.

2 4
50 2
40 1

171

Hint

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