[POI2005] BAN-Bank Notes

题目描述

`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

说明

对于 $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$。