--- tags: 問題 --- # D - Dagashiya 実行時間制限 : 2sec / メモリ制限 : 1024MB 配点 : $400$点 ## 問題文 デカビタくんは$K$円持って近所の駄菓子屋さんに行きました。その駄菓子屋さんには$N$個の商品が並んでいて、$i$番目の商品の値段は$A_i$円です。 また、それぞれの商品の在庫は無限にあります。 デカビタくんはそこでお菓子を買おうとしていますが、余ったお金はお母さんに返さないといけないため、限界までお金を使いたいと考えています。 デカビタくんはこの駄菓子屋で最大何円まで使うことができますか？ またそのような金額になるような商品の買い方を一つ答えてください。 ## 制約 * $1\leq N\leq3000$ * $1 \leq K \leq 5000$ * $1 \leq A_i \leq 5000$ * 入力はすべて整数 ## 入力 入力は以下の形式で標準入力から与えられる。 ``` N K A_1 A_2 ・・・ A_N ``` ## 出力 1行目に最大の金額を出力し、2行目に空白区切りで$i$番目の商品を何個買うかを出力してください。 ## 入力例1 ``` 5 1000 1 2 3 4 5 ``` ## 出力例1 ``` 1000 1000 0 0 0 0 ``` デカビタくんは商品1を1000個買うことで1000円を使い切ることができます。 ## 入力例2 ``` 8 342 261 402 329 263 70 84 166 30 ``` ## 出力例2 ``` 342 0 0 0 0 0 3 0 3 ```