2881: 「一本通 5.5 例 5」Banknotes
Memory Limit:512 MB
Time Limit:1 S
Judge Style:Text Compare
Creator:
Submit:24
Solved:10
Description
原题来自:POI 2005
Byteotian Bit Bank (BBB) 拥有一套先进的货币系统,这个系统一共有 $n$ 种面值的硬币,面值分别为 $b_1, b_2,\cdots , b_n$ 。但是每种硬币有数量限制,现在我们想要凑出面值 $k$,求最少要用多少个硬币。
Input
第一行一个数 $n$;
接下来一行 $n$ 个整数 $b_1, b_2,\cdots , b_n$ ;
第三行 $n$ 个整数 $c_1,c_2,\cdots ,c_n$ ,表示每种硬币的个数;
最后一行一个数 $k$,表示要凑的面值数。
Output
第一行一个数,表示最少需要付的硬币数。
Sample Input Copy
3
2 3 5
2 2 1
10
Sample Output Copy
3
HINT
对于全部数据,$1 \leq n \leq 200$,$1 \leq b_1 < b_2 < \cdots < b_n \leq 2 \times 10^4$,$1 \leq c_i, k \leq 2 \times 10^4$ 。