题目描述
Byteotian Bit Bank (BBB) 拥有一套先进的货币系统,这个系统一共有n种面值的硬币,面值分别为b1, b2,..., bn. 但是每种硬币有数量限制,现在我们想要凑出面值k,求最少要用多少个硬币。
输入格式
第一行一个数 n, 1≤n≤200。 接下来一行 n 个整数b1, b2,..., bn, 1≤b1﹤b2﹤ ...﹤bn≤20 000。 第三行 n 个整数c1, c2,..., cn, 1≤ci≤20 000, 表示每种硬币的个数。 最后一行一个数k – 表示要凑的面值数量, 1≤k≤20 000。
输出格式
第一行一个数表示最少需要付的硬币数。
样例输入
3
2 3 5
2 2 1
10
样例输出
3
数据规模与约定
对100%的数据, 1≤n≤200,1≤b1﹤b2﹤ ...﹤bn≤20 000,1≤ci,k≤20 000。