You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

原题来自：POI 2005

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

输出格式

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

样例

3
2 3 5
2 2 1
10

3

数据范围与提示

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