Bank Notes

Time limit3sMemory limit128 MB

Summary

With bounded supplies of each note denomination, find the fewest notes that sum exactly to k.

Level: Medium7 of 10
Topics: Dynamic programming, Greedy
Solved: No attempts yet

Problem

A bank in Byteotia runs the largest network of cash dispensers in the country. The bank wants every dispenser to pay out any requested amount using as few banknotes as possible.

The banknote denominations in circulation are $b_1, b_2, \ldots, b_n$ . Each dispenser holds $c_i$ notes of denomination $b_i$ .

Given, on standard input, the dispenser's stock of notes and the amount to be paid, write a program that determines the minimal total number of banknotes needed to pay the amount exactly.

Input

The first line contains the number of denominations $n$ ( $1 \le n \le 200$ ).

The second line contains $n$ integers $b_1, b_2, \ldots, b_n$ separated by single spaces ( $1 \le b_1 < b_2 < \cdots < b_n \le 20000$ ).

The third line contains $n$ integers $c_1, c_2, \ldots, c_n$ separated by single spaces ( $1 \le c_i \le 20000$ ); $c_i$ is the number of notes of denomination $b_i$ left in the dispenser.

The fourth line contains the amount to be paid $k$ ( $1 \le k \le 20000$ ). It is guaranteed that $k$ can be paid exactly with the available notes.

Output

Output a single integer: the minimal total number of banknotes needed to pay the amount $k$ exactly.

Examples3

Example 1
Input
```
3
2 3 5
2 2 1
10
```
Expected output
```
3
```
Example 2
Input
```
3
1 5 10
10 3 2
20
```
Expected output
```
2
```
Example 3
Input
```
3
1 3 4
10 10 10
6
```
Expected output
```
2
```