3922. 纸币

现有 $n$ 种面值的纸币,其中第 $i$ 种纸币的面值为 $b_i$,数量为 $c_i$。

现在,要用这些纸币凑出正好 $k$ 元钱。

请问,最少需要使用多少张纸币。

输入格式

第一行包含整数 $n$。

第二行包含 $n$ 个整数 $b_1,b_2,…,b_n$。

第三行包含 $n$ 个整数 $c_1,c_2,…,c_n$。

第四行包含一个整数 $k$。

输出格式

一个整数 $m$,表示最少需要使用的纸币数量。

数据范围

$1 \le n \le 200$,
$1 \le b_1 < b_2 < … < b_n \le 20000$,
$1 \le c_i \le 20000$,
$1 \le k \le 20000$。

输入样例:

3
2 3 5
2 2 1
10

输出样例:

3