Dotcpp  >  编程题库  >  信息学奥赛一本通T1601-Banknotes
题目 2503:

信息学奥赛一本通T1601-Banknotes

时间限制: 2s 内存限制: 192MB 提交: 13 解决: 4

题目描述

原题来自:POI 2005

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

输入格式

第一行一个数 n;

接下来一行 n 个整数 b1,b2,⋯,bn ;

第三行 n 个整数 c1,c2,⋯,cn ,表示每种硬币的个数;

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

输出格式

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

样例输入

3
2 3 5
2 2 1
10

样例输出

3

提示

数据范围与提示:

对于全部数据,1≤n≤200,1≤b1<b2<⋯<bn≤2×104,1≤ci,k≤2×104
标签