Tsukerkoman
Andrii, a true sweets lover, buys everything he sees when he goes to the store. Specifically, on each of his visits he buys candies with consecutive numbers from to .
Tomorrow, Andrii is going to a very important event - the final of UJGOI, so he wants to take as many candies with him as possible. He knows that the candy with number weighs grams, and his backpack can carry up to grams. There were a total of visits to the store, each of which he can buy candies from the interval . Tell him the maximum number of candies he can take with him, if he can take no more than candies with number .
Input
The first line contains two integers () and () - the number of visits to the store and the maximum weight Andrii's backpack can carry in grams.
The next lines each contain two integers and ().
Output
Output a single integer - the answer to the problem.
Examples
Note
Explanation for the first example:
The list of all candies Andrii bought is .
One of the options to take candies is .
Explanation for the second example:
One of the options to take candies will be , the total weight will be 20 grams.