题目描述

原题来自：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≤n≤200，1≤b_1<…<b_n≤20000，1≤c_i≤20000，0≤k≤20000。每种纸币最多取c_i张；必须恰好凑出k。k=0输出0，不能凑出输出-1；否则输出最少张数。

本地修订与来源

本题为经授权补全的本地训练修订版，原始公开题面保留在采集档案；修订了：1≤n≤200，1≤b_1<…<b_n≤20000，1≤c_i≤20000，0≤k≤20000。每种纸币最多取c_i张；必须恰好凑出k。k=0输出0，不能凑出输出-1；否则输出最少张数。。此处题意、范围和输出约定以本修订版为准，不冒称原站或官方原版。原题链接：https://ybt.ssoier.cn/problem_show.php?pid=1601。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共6个测试点，非原站或官方原始数据。总分100分。