### Problem Statement

When a customer buys large quantities of a product, frequently the seller will offer a volume discount. For instance, one unit might cost 10 dollars, but might be offered in packages of 5 for 45 dollars. In such a case, it always makes sense buy the bulk lots to save money. In some other cases, however, it might not always make sense. Suppose a single unit were on sale for 8 dollars. In such a case, purchasing single units would be less expensive than purchasing a 5-pack.

You are given a String[] priceList describing the number of units available in each bundle, and the cost of the bundle. Each element is of the form "units cost" (quotes added for clarity). You are also given an int quantity, the number of units you wish to purchase.

Return an int indicating the best possible cost to purchase at least the desired quantity of units.

### Definition

 Class: VolumeDiscount Method: bestDeal Parameters: String[], int Returns: int Method signature: int bestDeal(String[] priceList, int quantity) (be sure your method is public)

### Constraints

-priceList will contain between 1 and 5 elements, inclusive.
-Each element of priceList will be formatted as described in the problem statement.
-units will be an integer between 1 and 99, inclusive, with no leading zeroes
-cost will be an integer between 1 and 999, inclusive, with no leading zeroes.
-No two values of units will be the same.
-quantity will be between 1 and 99, inclusive.

### Examples

0)

 `{"1 10", "5 45"}` `10`
`Returns: 90`
 The first example suggested in the problem statement.
1)

 `{"1 8", "5 45"}` `10`
`Returns: 80`
 The second example suggested in the problem statement.
2)

 `{"99 913", "97 173", "50 464", "80 565"} ` `18`
`Returns: 173`
 Here, every package has more units than we need, so we pick the cheapest one.
3)

 `{"2 272","1 166","10 993"}` `81`
`Returns: 8110`

#### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=5945

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=8073&pm=5945

timmac

#### Testers:

PabloGilberto , brett1479 , Olexiy

#### Problem categories:

Brute Force, Recursion