Candy Store#6210
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 available in unlimited quantity, so you can buy any amount. You can buy only an integer number of candies.
The input consists of multiple test cases. The first line of each test contains the number of different types of candies (1 \le n \le 5000) and the amount of money (0.01 \le m \le 100.00), which you can spend. The amount of money is expressed in dollars with two decimal places and no leading zeros unless the amount is less than a dollar. Each of the following lines contains an integer (1 \le c \le 5000) and the amount of money (0.01 \le p \le 100.00). Here, is the number of calories per item, and is its price in dollars in the same format as . The last line contains and should not be processed.
For each test case, print on a separate line the maximum number of calories that can be bought for up to dollars, inclusive.
Example 1