A5595. 「一本通 5.5 例 5」Banknotes
编程题
普及/提高-
知识点
题目描述
**原题来自：POI 2005**
Byteotian Bit Bank (BBB) 拥有一套先进的货币系统，这个系统一共有 $n$ 种面值的硬币，面值分别为 $b_1, b_2,\cdots , b_n$。但是每种硬币有数量限制，现在我们想要凑出面值 $k$，求最少要用多少个硬币。
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$，表示要凑的面值数。
接下来一行 $n$ 个整数 $b_1, b_2,\cdots , b_n$；
第三行 $n$ 个整数 $c_1,c_2,\cdots ,c_n$，表示每种硬币的个数；
最后一行一个数 $k$，表示要凑的面值数。
输出格式
第一行一个数表示最少需要付的硬币数。
输入输出样例
输入 #1
3 2 3 5 2 2 1 10
输出 #1
3
说明/提示
对于全部数据，$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$。