题目描述

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。