Fortress Defense

The wall of a besieged fortress consists of $n$ sections numbered from 1 to $n$. Reconnaissance reports that in the next assault the enemy will send $a_i$ soldiers to attack section $i$. To defend the fortress, $s$ defenders will be sent to the sections of the wall.

The sections differ in the quality of their fortifications, which makes defense effectiveness differ as well. One defender in section $i$ can repel the attack of $k_i$ attackers.

Suppose $x_i$ defenders are sent to section $i$. If the number of attackers does not exceed $x_i \cdot k_i$, then no attacker breaks into the fortress through this section. Otherwise, $a_i - x_i \cdot k_i$ attackers break into the fortress.

Write a program that distributes the defenders among the sections so that their total number equals $s$ and as few attackers as possible break into the fortress.

The first line contains integers $n$, the number of sections of the wall, and $s$, the number of defenders of the fortress ($1 \leq n \leq 100\,000$; $1 \leq s \leq 10^9$).

The next $n$ lines contain two integers each, $a_i$ and $k_i$, the total number of attackers on section $i$ of the wall and the number of attackers that one defender of this section can repel ($1 \leq a_i, k_i \leq 10^9$).

The output must contain a single integer: the minimum number of attackers that break into the fortress.

In the first test, if all 10 defenders are placed on the only section, they can repel all the attackers and nobody gets into the fortress. In the second sample, one can, for example, send two defenders to the first section and one to the third.