Crisis
«If I knew the trick, I'd live in Yalta»
Petro
During a crisis, the exchange rate of the national currency on the planet Olympia (olymp) began to fluctuate against the intergalactic currency (galact). Once the crisis was over, Petro, a resident of the planet, wanted to calculate how much he could have earned with his initial savings if he had known the daily exchange rates in advance.
Your task is to write a program that, given Petro's initial savings in olymps and the daily fluctuations of the olymp-to-galact exchange rate, determines the maximum amount of money Petro could have by the end of the crisis. Note that buying or selling fractional amounts of galacts is not allowed. By the end of the crisis, all funds must be converted back into olymps.
Input
The first line contains two integers: N (1 ≤ N ≤ 50000), representing the duration of the crisis in days, and S (1 ≤ S ≤ 100000), representing Petro's initial savings. The next N lines each contain two natural numbers, both not exceeding 1000000:
The first number indicates the number of olymps required to purchase one galact on that day.
The second number indicates the number of olymps received by selling one galact on that day. The second number is always less than or equal to the first.
Output
Output a single integer representing the maximum amount of olymps Petro could have at the end of the last day of the crisis. It is guaranteed that the answer for each test will not exceed 10^18.