提示: 欢迎访问OurACM平台。
Problem 1432 Coin Changing

Accept: 359    Submit: 1020
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

There are n kinds of coins. Given the available number of coins for each kind, you are to calculate the minimal number of coins needed to exchange m yuan.

Input

There are several test cases. The fist line of each case contains an integer n (1<=n<=10). Followed n lines, each line contains two integers representing the cost and the available number of coins of this kind respectively. The last line of each case contains an integer m (1<=m<=20001) representing the given amount of money you have to exchange.

Output

Please output the minimal number of coins needed to exchange the money. If you can't exchange the given amount of money, please output -1.

Sample Input

3 1 3 2 3 5 3 18

Sample Output

5

Source

FZU 2006 Summer Training II

Submit  Back  Status  Discuss