3253 - Bank notes

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

输入

第一行一个数n(1≤n≤200)。

接下来一行n个整数b1,b2…bn(1≤b1

第三行n个整数c1,c2…cn(1≤ci≤20000),表示每种硬币的个数。

最后一行一个数k表示要凑的面值数(1≤k≤20000)。

输出

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

样例

输入

3
2 3 5
2 2 1
10

输出

3

来源

动规专题

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题