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 $ を満たす必要があります。

### Sample Explanation 1 $ 100 $ 円の硬貨を $ 1 $ 枚使うと、最終的に所持する硬貨の枚数は $ 5 $ 枚となります。 $ 4 $ 枚以下となる支払い方はできないので、これが答えの一例となります。 ### Sample Explanation 2 $ 50 $ 円の硬貨を $ 2 $ 枚、 $ 5 $ 円の硬貨を $ 2 $ 枚使うと、最終的に所持する硬貨の枚数は $ 9 $ 枚となります。 $ 8 $ 枚以下となる支払い方はできないので、これが答えの一例となります。 また、以下の支払い方でも $ 9 $ 枚は達成できますが、 $ 10 $ 円の硬貨を支払いに使い、おつりでも受け取るので、支払い方の条件を満たしません。 ``` 0 2 1 2 0 0 ``` ### Constraints - 入力はすべて整数 - $ 1\leq N\leq 30 $ - $ 1=C_1