B - おつり 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 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