Dasom's Shoe Store

Dasom runs a shoe store. The store sells popular shoes and also less popular add-on items that work like discount coupons. If you buy one add-on item for C won, you receive a D% discount on the shoe you want to buy. The discount rate D is one of 1, 2, or 3.

When you buy several add-on items, their discounts are applied one after another. A 2% discount followed by a 3% discount changes an original price X into X * 0.98 * 0.97. The money spent on the add-on items is also part of the total amount paid.

Given the price and discount rate of each add-on item, and the original price of the shoe you want, find the minimum total amount you must pay.

The first line contains the number N of add-on items and the original price S of the shoe you want to buy. N is a positive integer no greater than 50, and S is a positive integer no greater than 1,000,000,000.

Each of the next N lines contains the price C of an add-on item and its discount rate D. C is a positive integer no greater than 10,000,000, and D is one of 1, 2, or 3.

Output the minimum total amount that must be paid to buy the shoe. An absolute or relative error of at most 10^-6 is accepted.

Because the add-on items themselves also cost money, buying every discounted item is not always optimal. Items with the same discount rate have the same effect, so after fixing how many items of a rate to buy, it is best to choose the cheapest ones of that rate.