Maximizing Weighted Score for Final Exam Preparation

Huaijiao is preparing for his final exams which span n courses. With only M days left, he wants to plan a quick review (speed‐through) schedule that maximizes his overall weighted score.

For each course i (1 ≤ i ≤ n), you are given its credit c_i and difficulty coefficient k_i. If Huaijiao spends x days on course i, he will obtain a score computed as:

$$w_i = \min\Bigl(1,\frac{x}{k_i}\Bigr)\times 100$$

The final weighted score is then:

$$W = \sum_{i=1}^{n} \Bigl(w_i\times c_i\Bigr)$$

Each day, Huaijiao can focus on only one course. Note that for each course, spending more than k_i days does not improve its score (i.e. the score saturates at 100). Your task is to help him allocate his days wisely across the courses so as to maximize the total weighted score W.

Hint: Observe that if you invest days into course i, each day brings an incremental score of 100\cdot c_i/k_i until the course is fully reviewed (i.e. until you have invested k_i days).

inputFormat

The first line contains two integers n and M -- the number of courses and the total number of days available.

Then, n lines follow. Each line contains two integers ci and ki representing the credit and difficulty coefficient for the i^th course respectively.

It is guaranteed that 1 ≤ n ≤ 10⁵, 1 ≤ M ≤ 10⁹, and 1 ≤ ci, ki ≤ 10⁴. (The constraints above are illustrative; adjust as needed.)

outputFormat

Output a single number -- the maximum total weighted score Huaijiao can achieve. Answers within an absolute or relative error of 10^-6 will be accepted.

sample

2 3
3 2
4 4

400