Candy Store

Walking with a friend, you accidentally pass by a candy store. How unhealthy sweets are! Each of you enters the store with the same amount of money. Whoever buys the candy with the most total calories wins.

Since you are a smart scientist, you have access to the goods of the confectionery. You decide to write a program that will determine the maximum number of calories you can buy. For each product, the price and the number of calories are known. Each product is enough in stock, so you can buy any quantity. You can buy only aт штеупук number of sweets.

Input

Consists of multiple test cases. The first line of each test contains the number of different types of candies $n(1\le n\le 5000)$ and amount of money $m(0.01\le m\le 100.00)$, hat you can spend. Amount of money $m$ is expressed in dollars with two decimal places and no leading zeros unless the amount is less than a dollar. Each of the following $n$ lines contain an integer $c(1\le c\le 5000)$ and the amount of money $p(0.01\le p\le 100.00)$. Here $c$ is the number of calories per item, and $p$ is its price in dollars in the same format as $m$. The last line contains $00.00$ and should not be processed.

Output

For each test case, print on a separate line the maximum number of calories that can be bought for up to $m$ dollars, inclusive.

Examples