L3423 [POI 2005] BAN-Bank Notes

• 所属训练：T2967 2026盖世计划-D班前置训练【专题 4：DP 优化】
• 训练内顺序：10
• 原题链接：打开梦熊 OJ 题面
• 难度：普及+/提高
• 时间限制：1000 ms
• 内存限制：62 MB
• 输入输出类型：standard
• 判题方式：text
• 标签：动态规划 DP、2005、POI（波兰）、Special Judge

题目描述

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

输入格式

第一行一个整数 $n$。

第二行 $n$ 个整数 $b_i$，表示这 $n$ 种硬币的面值。

第三行 $n$ 个整数 $c_i$，表示这 $n$ 种硬币的数量。

第四行一个整数 $k$。

输出格式

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

第二行 $n$ 个整数，表示第 $i$ 种硬币需要多少个。

如果有多种方案，输出其中一种即可。

样例

样例 1 输入

3
2 3 5
2 2 1
10

样例 1 输出

3
1 1 1

1
1
1
1

1
1

2
9 10
1 3
29

3
1 2

说明与提示

数据范围

对于 $100\%$ 的数据，$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$。