## 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