There's a shoe store in which some models are popular, and some are not. In order to sell more unpopular models, the store introduced a system of discounts. Each discount works in the following way: if you buy an unpopular model for a cost of *COST*, then you can buy a popular model with a *PERCENT*% discount. However, the owner of the store is greedy, and therefore only discounts with *PERCENT*s equal to 1, 2 and 3 were introduced.
After it became obvious that such low discounts didn't work well, the store allowed people to apply more than one discount to the same pair of shoes. For example, you can buy three unpopular models, obtain three discounts and use all three to reduce the cost of the same popular model. When many discounts are applied to the same model, they are applied one after another. For example, if you apply 2% and 3% discounts to a model with cost 100, it's cost will be 0.98 * 0.97 * 100 = 95.06.
The available discounts are given in a String[] **discounts**, each element of which is formatted "COST PERCENT" (quotes for clarity). Different elements of **discounts** correspond to different unpopular models. You want to buy a popular model, which costs **price**. In order to reduce the model's cost, you can buy some unpopular models and obtain discounts from them, but you don't wish to buy the same unpopular model more than once. Return the minimum amount of money you need to spend in order to buy the desired popular model. |