问题 R: 的货币系统Banknotes

内存限制:128 MB 时间限制:1 S
题面:传统 评测方式:文本比较 上传者:
提交:56 通过:11

题目描述

原题来自:POI 2005
Byteotian Bit Bank (BBB) 拥有一套先进的货币系统,这个系统一共有 n 种面值的硬币,面值分别为 b1,b2,...bn。但是每种硬币有数量限制,现在我们想要凑出面值 k,求最少要用多少个硬币。

输入格式

输入格式
第一行一个数 n;
接下来一行 n 个整数b1,b2,...bn;
第三行 n个整数 ,c1,c2,..cn表示每种硬币的个数;
最后一行一个数 kk,表示要凑的面值数。

输出格式

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


输入样例 复制

3
2 3 5
2 2 1
10

输出样例 复制

3

分类标签