配点 : 100 点
問題文
目前在 NUPC 国家 N 流通中的硬币种类繁多,其价值为 C_1, C_2, \dots, C_N 这是日元。
您将依次收到这些硬币。 A_1, A_2, \dots, A_N 我每一个都有。
你 M 我想购买价值 ¥ 的产品。 商店单独存放所有硬币。 10^{100} 我各有一个,M 如果您支付的金额超过日元,则将以最低数量的硬币支付找零。 (在这个问题的约束下,唯一确定了这种支付方式。)
此外,不支持将支付时使用的硬币作为找零退回的支付方式。 例如,10 使用日元硬币进行支付和找零。 10 无法使用日元硬币进行支付。
您希望最大限度地减少购买产品后剩余的硬币数量。 请输出一个最小化手头剩余硬币数量的支付方式示例。 是
制約
- 输入全部为整数
- 1\leq N\leq 30
- 1=C_1<C_2<\cdots<C_N\leq 10^9
- C_{i+1} 是 C_{i} 的倍数 (1\leq i\leq N-1)
- 0\leq A_i\leq 10^9 (1\leq i\leq N)
- 1\leq M\leq \sum_{i=1}^N {C_i \cdot A_i}
入力
输入如下格式从标准输入给出。
N M C_1 C_2 \dots C_N A_1 A_2 \dots A_N
出力
请输出付款方式示例如下。
m_1 m_2 \dots m_N
这里 m_1, m_2, \dots, m_N 是支付的每个硬币的数量, 0\le m_i \le A_i (1\le i \le N)和 必须满足 \sum_{i=1}^N C_i \cdot m_i \geq M 。
入力例1
6 100 1 5 10 50 100 500 1 1 1 1 1 1
出力例1
0 0 0 0 1 0
100 日元硬币 当您使用 1 金币时,您最终拥有的金币数量为 5 件。 这是答案的示例,因为不可能支付低于4 的费用。
入力例2
6 100 1 5 10 50 100 500 2 2 2 2 2 2
出力例2
0 2 0 2 0 0
50 日元硬币 当您使用 2 枚、5 日元硬币 当您使用 2 金币时,您最终拥有的金币数量为 9 件。 这是答案的示例,因为不可能支付低于8 的费用。
您还可以使用以下付款方式。 9 可以实现,但是10 由于我使用日元硬币付款并收到零钱,因此不符合付款方式条件。
0 2 1 2 0 0
入力例3
4 1000 1 100 500 1000 2000 0 0 0
出力例3
2000 0 0 0