「一本通 5.5 例 5」Banknotes

【题目描述】

原题来自：POI 2005

Byteotian Bit Bank (BBB) 拥有一套先进的货币系统，这个系统一共有 $n$ 种面值的硬币，面值分别为 $b\_1, b\_2,\\cdots , b\_n$ 。但是每种硬币有数量限制，现在我们想要凑出面值 $k$，求最少要用多少个硬币。

【输入】

第一行一个数 $n$；

接下来一行 $n$ 个整数 $b\_1, b\_2,\\cdots , b\_n$ ；

第三行 $n$ 个整数 $c\_1,c\_2,\\cdots ,c\_n$ ，表示每种硬币的个数；

最后一行一个数 $k$，表示要凑的面值数。

【输出】

第一行一个数表示最少需要付的硬币数。

【输入样例】

3
2 3 5
2 2 1
10

【输出样例】

3

【提示】

数据范围与提示:

对于全部数据，$1≤n≤200,1≤b\_1 < b\_2 < ⋯ < b\_n ≤2×10^4 ,1≤c\_i ,k≤2×10^4$ 。

【来源】

一本通在线评测