题目描述

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，表示要凑的面值数。

输出描述

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

示例1

输入

3
2 3 5
2 2 1
10

输出

3

备注

对于全部数据，$1 \leq n \leq 200,1 \leq b_1 \lt b_2 \lt \cdots \lt b_n \leq 2 \times10^4,1 \leq c_i,k \leq 2 \times10^4$。