Byteotian Bit Bank (BBB) 拥有 Byteotia 最大的自动取款机网络。BBB 决定改进他们的取款机，并向你寻求帮助。Byteotia 的法定货币面额为 $b_1, b_2, \dots, b_n$。BBB 决定让取款机以最少的纸币总数支付每一笔金额。

编写一个程序：

• 从标准输入读取取款机中纸币库存的描述以及需要支付的金额。
• 确定支付所需金额的最少纸币总数，并找到一种支付方式（当然，要使用确定的最少纸币数量）。
• 将结果写入标准输出。

输入格式

标准输入的第一行包含面额数量 $n$，$1 \le n \le 200$。第二行包含 $n$ 个整数 $b_1, b_2, \dots, b_n$，$1 \le b_1 < b_2 < \dots < b_n \le 20\,000$，由空格分隔。第三行包含 $n$ 个整数 $c_1, c_2, \dots, c_n$，$1 \le c_i \le 20\,000$，同样由空格分隔；$c_i$ 是取款机中面额为 $b_i$ 的纸币数量。最后第四行包含一个整数 $k$，表示需要支付的金额，$1 \le k \le 20\,000$。对于测试数据，你可以假设金额 $k$ 可以用现有的纸币支付。

输出格式

第一行应包含一个整数，表示支付金额 $k$ 所需的最少纸币总数。第二行应包含 $n$ 个由空格分隔的整数，表示支付金额 $k$ 时所使用的各面额纸币的数量。如果存在多种方案，程序可以输出其中任意一种。

样例

输入 1

3
2 3 5
2 2 1
10

输出 1

3
1 1 1