题目描述

原题来自：POI 2005

Byteotian Bit Bank (BBB) 拥有一套先进的货币系统，这个系统一共有 $\red{n}$ 种面值的硬币，面值分别为$\red{ b_1, b_2,\cdots , b_n}$。但是每种硬币有数量限制，现在我们想要凑出面值 $\red{k}$，求最少要用多少个硬币。

输入格式

第一行一个数 $\red{n}$；

接下来一行 $\red{n}$ 个整数 $\red{b_1, b_2,\cdots , b_n}$​；

第三行$\red{ n}$ 个整数 $\red{c_1,c_2,\cdots ,c_n}$​，表示每种硬币的个数；

最后一行一个数$\red{ k}$，表示要凑的面值数。

输出格式

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

样例

输入样例

3
2 3 5
2 2 1
10

输出样例

3

提示

对于全部数据，$\red{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}$。