题目描述

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$，表示要凑成的目标面值。

输出格式

一行一个整数，表示凑出 $k$ 所需的最少硬币数。如果无法凑出 $k$，则输出 $-1$（题目未明说，但通常如此；此处仅输出最少硬币数，假设数据保证有解）。

样例

3
2 3 5
2 2 1
10

3

数据范围与提示

• $1 \le n \le 200$
• $1 \le b_1 < b_2 < \cdots < b_n \le 2 \times 10^4$
• $1 \le c_i \le 2 \times 10^4$
• $1 \le k \le 2 \times 10^4$

来源

一本通 5.5 例 5