Maximizing Revenue from Scenic Spots

Facer's father is a manager who is currently distraught because his company is in trouble. The company manages \(n\) scenic spots, each attracting many visitors. Recently, tourists have complained about high ticket prices, forcing him to adjust them.

For the \(i\)th scenic spot, if the ticket price is \(x\), the number of visitors is given by:

\(\max(a_i - b_i \times x,\,0)\)

The revenue from the \(i\)th scenic spot is therefore:

\(x \times \max(a_i - b_i \times x,\,0)\)

You are required to assign a ticket price for each scenic spot such that the sum of the ticket prices does not exceed \(k\). Your task is to compute the maximum total revenue that can be obtained from all scenic spots.

inputFormat

The first line contains two integers \(n\) and \(k\) (the number of scenic spots and the maximum total ticket price allowed).

Each of the following \(n\) lines contains two integers \(a_i\) and \(b_i\) describing the parameters for the \(i\)th scenic spot.

It is guaranteed that for each scenic spot, if the ticket price is \(x\), the number of visitors is \(\max(a_i - b_i \times x, 0)\).

outputFormat

Output a single integer representing the maximum total revenue that can be obtained under the given constraints.

sample

3 10
10 2
12 1
15 3

66