AT_nupc2024_b.おつり

NUPC 国目前流通有 $N$ 种硬币，面值分别为 $C_1, C_2, \dots, C_N$ 日元。

你分别拥有 $A_1, A_2, \dots, A_N$ 枚这些硬币。

你想要购买一件价格为 $M$ 日元的商品。商家对每种硬币都各自拥有 $10^{100}$ 枚，如果你支付的金额超过 $M$，找零会以使找回的硬币总数最少的方式进行支付。（在本题的条件下，这种找零方式是唯一的。）

此外，支付时不得出现你支付出去的硬币作为找零返还的情况。 例如，若你用一枚 $10$ 日元硬币支付，找零中不能包含 $10$ 日元硬币。

你希望购买商品后，自己手里剩余的硬币数尽可能少。请输出一种剩余硬币数最少的支付方案。

输入通过标准输入按以下格式给出。

$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

如果用 $1$ 枚 $100$ 日元硬币支付，最终你手里还剩 $5$ 枚硬币，无法使用更少的硬币支付。因此，这是一个满足条件的支付方案例。

样例解释 2

如果用 $2$ 枚 $50$ 日元、$2$ 枚 $5$ 日元硬币支付，最终你手里还剩 $9$ 枚硬币，无法使用更少的硬币支付。因此，这是一个满足条件的支付方案例。

另外，以下支付方式虽然也能使剩余硬币数量为 $9$ 枚，但由于其中 $10$ 日元硬币既被用于支付也被用于找零，不满足题目的支付条件：

0 2 1 2 0 0

数据范围

• 所有输入均为整数
• $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$

由 ChatGPT 5 翻译