Description

Original Source: POI 2005

Byteotian Bit Bank (BBB) has an advanced monetary system consisting of $n$ denominations of coins, with face values of $b_1, b_2,\cdots , b_n$. However, each type of coin has a limited quantity. Now, we want to make up the amount $k$ using the fewest number of coins possible.

Input Format

The first line contains a number $n$;

The second line contains $n$ integers $b_1, b_2,\cdots , b_n$;

The third line contains $n$ integers $c_1,c_2,\cdots ,c_n$, representing the quantities of each type of coin;

The last line contains a number $k$, the target amount to be formed.

Output Format

The first line should output the minimum number of coins required.

Sample 1

3
2 3 5
2 2 1
10

3

Data Range and Hints

For all data, $1\le n\le 200,1\le b_1\lt b_2\lt \cdots \lt b_n\le 2\times 10^4,1\le c_i,k\le 2\times 10^4$.