M. Tower of the Sorcerer
time limit per test
4 с
memory limit per test
512 megabytes
input
standard input
output
standard output

It may seem that the story is usual. A warrior is trying to save the princess caught in the tower. But this is not a usual ordinary story. Well, this story is even not from this game.

Tower of the Sorcerer appears to be RPG-style; you have a strength (STR) and a health bar showing the health points (HP), and so do all the monsters. When you engage a monster, you and the monster take turns hitting each other until one falls, and you go first. Each attack will cause damages that make the health point of the one being attacked decreased by the strength of the attacker. A character falls if its health point drops to zero or lower after an attack.

As an excellent hacker and a player manipulating the warrior, you set your initial health point as infinity. There are $$$n$$$ monsters inside the tower. You can fight against the monsters in any order. After defeating a monster, you can set your strength to the strength of the defeated monster.

What is the minimum total amount of damages you will receive?

Input

The first line contains two integers $$$n$$$ $$$(1 \leq n \leq 10^5)$$$ and $$$STR_w$$$ $$$(1 \leq STR_w \leq 10^5)$$$, indicating the number of monsters and the initial strength of the warrior.

In the next $$$n$$$ lines, the $$$i$$$-th line contains two integers $$$STR_i$$$ and $$$HP_i$$$ $$$(1 \leq STR_i, HP_i \leq 10^5)$$$, representing the strength and the health point of the $$$i$$$-th monster.

Output

Output an integer in a line, representing the minimum total amount of damages the warrior will receive.

Example
Input
4 1
3 2
4 4
5 6
1 6
Output
9
Note

For the sample case:

  1. You, the warrior, attack the first monster; the monster receives $$$1$$$ damage. The first monster starts to attack you, causing $$$3$$$ damages. You attack the first monster once again; it receives $$$1$$$ more damage and falls. Then you set your strength to $$$3$$$.
  2. You attack the fourth monster; the monster receives $$$3$$$ damages. The fourth monster starts to attack you, causing $$$1$$$ damage. You attack the fourth monster once again; it receives $$$3$$$ more damages and falls.
  3. You attack the third monster; it receives $$$3$$$ damages. The third monster starts to attack you, causing $$$5$$$ damages. You attack the third monster once again; it receives $$$3$$$ more damages and falls. Then you set your strength to $$$5$$$.
  4. You attack the second monster; it receives $$$5$$$ damages and falls. Then the game ends, and you receives $$$9$$$ damages in total.