题目描述
原题来自：POI 2005
Byteotian Bit Bank (BBB) 拥有一套先进的货币系统，这个系统一共有
n
n 种面值的硬币，面值分别为
b_1, b_2,\cdots , b_n
b1
,b2
,⋯,bn
。但是每种硬币有数量限制，现在我们想要凑出面值
k
k，求最少要用多少个硬币。
输入
第一行一个数
n
n；
接下来一行
n
n 个整数
b_1, b_2,\cdots , b_n
b1
,b2
,⋯,bn
；
第三行
n
n 个整数
c_1,c_2,\cdots ,c_n
c1
,c2
,⋯,cn
，表示每种硬币的个数；
最后一行一个数
k
k，表示要凑的面值数。
输出
第一行一个数表示最少需要付的硬币数。
样例输入
3
2 3 5
2 2 1
10
样例输出
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
1≤n≤200,1≤b1
<⋯≤2×104,1≤ci
,k≤2×104。
来源/分类
ybttg 背包DP