Buying Hay

Interview

Time limit1sMemory limit128 MB

Summary

Given N package types with unlimited supply, each weighing P_i and costing C_i, find the minimum total cost to buy at least H pounds of hay.

Level: Medium6 of 10
Topics: Dynamic programming, Greedy, Math, Brute force
Solved: No attempts yet

Problem

Farmer John is running low on supplies and needs to buy at least $H$ ( $1 \le H \le 50{,}000$ ) pounds of hay for his cows.

There are $N$ ( $1 \le N \le 100$ ) hay suppliers, conveniently numbered $1$ through $N$ . Supplier $i$ sells packages that each contain $P_i$ ( $1 \le P_i \le 5{,}000$ ) pounds of hay at a price of $C_i$ ( $1 \le C_i \le 5{,}000$ ) dollars. Every supplier has an unlimited number of packages, and each package must be bought whole (packages cannot be split).

Help Farmer John find the minimum cost required to buy at least $H$ pounds of hay.

Input

Line 1: Two space-separated integers $N$ and $H$ .
Lines 2 to $N+1$ : Line $i+1$ contains two space-separated integers $P_i$ and $C_i$ for supplier $i$ .

Output

Line 1: A single integer, the minimum cost Farmer John must pay to obtain at least $H$ pounds of hay.

Hint

For instance, buying three packages from the second supplier ( $5$ pounds each at $3$ dollars) yields $15$ pounds for a total cost of $9$ dollars.

Examples2

Example 1
Input
```
2 15
3 2
5 3
```
Expected output
```
9
```
Example 2
Input
```
1 10
2 3
```
Expected output
```
15
```