3454: 「一本通 5.5 例 5」Banknotes

内存限制:512 MB 时间限制:0.200 S
评测方式:文本比较 命题人:
提交:0 解决:0

题目描述

**原题来自:POI 2005** 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$,表示要凑的面值数。

输出

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

样例输入 复制

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$。

来源/分类