RPG Skill Upgrade Maximization

Little Blue is playing an RPG game. His character has N skills that can increase his attack power. The i^th skill, when upgraded for the first time, boosts the attack by $A_i$ points. For every subsequent upgrade of that skill, the increase in attack power decreases by $B_i$ points. In other words, the first upgrade gives an increase of $A_i$, the second gives $A_i - B_i$, the third gives $A_i - 2B_i$, and so on. After $\lceil\frac{A_i}{B_i}\rceil$ upgrades (where \(\lceil \cdot \rceil\) denotes the ceiling function), further upgrades for that skill will no longer increase the attack power.

Now Little Blue can perform a total of M upgrades. He may choose any skill and upgrade it any number of times (subject to each skill’s maximum effective upgrades as described above). Your task is to determine the maximum total increase in attack power that Little Blue can achieve.

inputFormat

The first line contains two integers N and M, representing the number of skills and the total number of upgrades available, respectively.

Each of the next N lines contains two integers A_i and B_i representing the initial attack power increase and the decrease per subsequent upgrade for the i^th skill.

outputFormat

Output a single integer representing the maximum total increase in attack power that can be obtained.

sample

1 3
10 3

21