E. Strongest Attack First
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In the underground, you must fight a funny skeleton. You must survive his strongest attack, which he will use first. His strongest attack consists of $$$n$$$ waves, and your soul starts with $$$h$$$ health points.

For his $$$i$$$-th wave,

  • the attack lasts $$$t_i$$$ seconds
  • the attack deals $$$d_i$$$ damage per second

Before the fight, you can set your player level to an integer $$$\ell$$$ that decreases the amount of damage you take. More specifically, an attack that originally deals $$$d_i$$$ damage per second will now deal $$$d_i - \ell$$$ damage per second. Note that damage per second cannot be negative, so if $$$\ell \ge d_i$$$ the $$$i$$$-th attack will just deal no damage.

You survive the strongest attack if, after all $$$n$$$ waves, your soul ends with positive HP. You don't want to waste time training more than you need to, so you want your player level to be as small as possible. Can you figure out what level you need to survive the skeleton?

Input

The first line contains two integers $$$n$$$ and $$$h$$$ $$$(1 \leq n \leq 2 \cdot 10^5, 1 \leq h \leq 10^9)$$$ — the number of attack waves and your soul's starting HP, respectively.

The next $$$n$$$ lines contain two integers, where $$$t_i$$$ is the duration and $$$d_i$$$ is the damage per second of the $$$i$$$-th attack $$$(1 \le t_i, d_i \le 10^9)$$$.

Output

Output a single integer, the minimum non-negative integer $$$\ell$$$ such that you will survive the attack.

Examples
Input
3 20
1 15
3 5
10 1
Output
3
Input
1 100
1 100
Output
1
Note

In the first test case, after training to level $$$\ell=3$$$, the first wave will do $$$1 \times (15-3) = 12$$$ damage, the second wave will do $$$3 \times (5-3) = 6$$$ damage, and the third wave will do $$$10 \times 0 = 0$$$ damage. So after the attack, the soul will have $$$20 - (12+6+0) = 2$$$ health points remaining. It can be shown that this is the minimum $$$\ell$$$ needed to survive the attack.

For the second test case, only $$$\ell=1$$$ is needed to survive the singular wave with $$$1$$$ health point remaining.