#P1531. [POI2005]Bank notes

    ID: 543 传统题 1000ms 256MiB 尝试: 998 已通过: 392 难度: 5 上传者: 标签>CF1800普及+/提高-多重背包单调队列优化多重背包滚动数组单调队列/单调栈优化

[POI2005]Bank notes

[POI2005] BAN-Bank Notes

题目描述

Byteotian Bit Bank(BBB) 拥有一套先进的货币系统,这个系统一共有 nn 种面值的硬币,面值分别为 b1,b2,⋯ ,bnb_1,b_2,\cdots,b_n。但是每种硬币有数量限制,现在我们想要凑出面值 kk,求最少要用多少个硬币。数据保证 kk 可以被凑出。

输入格式

第一行一个整数 nn。

第二行 nn 个整数 bib_i,表示这 nn 种硬币的面值。

第三行 nn 个整数 cic_i,表示这 nn 种硬币的数量。

第四行一个整数 kk。

输出格式

第一行一个整数,表示最少需要多少个硬币。

样例 #1

样例输入 #1

3
2 3 5
2 2 1
10

样例输出 #1

3

提示

对于 100%100\% 的数据

1≤n≤2001 \le n \le 200,1≤b1<b2<⋯<bn≤2×1041 \le b_1 < b_2 < \cdots < b_n \le 2 \times 10^4,1≤ci≤2×1041 \le c_i \le 2 \times 10^4,1≤k≤2×1041 \le k \le 2 \times 10^4

题解