No.31 悪のミックスジュース
LayCurse問題文
ミックスジュースが切れました。
ミックスジュースの原材料の表示は、順番に、果物 \(1\)，果物 \(2\)，\(\ldots\)，果物 \(N\) となっています。
既存のそれぞれの果物の100%ジュースを混ぜてミックスジュースを \(V\) リットルだけ作りたいです。
果物 \(k\) の100%ジュースは \(1\) リットルパックのみが売られていて、\(1\) パックあたり \(C_k\) 円です。
\(V\) リットルのミックスジュースを、原材料の表示を変更することなく作るための、最小コストを求めるプログラムを書いてください。
つまり、ミックスジュースにおいて果物 \(k\) が占める割合 \(p_k\) は \(p_1 \geq p_2 \geq \cdots \geq p_N\) となる必要があり、更に、使われない果物があってもいけません。
\(1\) リットルパックを買い、その一部のみを使用することも可能です。
入力
\(N\) \(V\) \(C_1\) \(C_2\) ... \(C_N\)
\(1\) 行目では、果物の種類数を表す整数 \(N\ (1 \leq N \leq 100)\) と作りたいミックスジュースの量を表す整数 \(V\ (1 \leq V \leq 10^9)\) が与えられます。
\(2\) 行目では、果物 \(k\) の100%ジュースの \(1\) リットルパックの値段を表す整数 \(C_k\ (1 \leq C_k \leq 10^9)\) が順番にスペース区切りで与えられます。
出力
最小のコスト（単位は円）を表す整数を \(1\) 行で出力せよ。最後に改行すること。
サンプル
サンプル1
入力
3 10 1 100 100
出力
208
果物 \(1\) を \(8\) リットル、果物 \(2,3\) をそれぞれ \(1\) リットル混ぜるのが最適です。
サンプル2
入力
3 10 100 1 100
出力
604
果物 \(1\) を \(5\) リットル、果物 \(2\) を \(4\) リットル、果物 \(3\) を \(1\) リットル混ぜるのが最適です。
サンプル3
入力
3 10 100 100 1
出力
703
果物 \(1\) を \(4\) リットル、果物 \(2\) を \(3\) リットル、果物 \(3\) を \(3\) リットル混ぜるのが最適です。
サンプル4
入力
3 1 100 100 100
出力
300
例えば、\(3\) つ全ての果物の \(1\) リットルパックを買い、果物 \(1\) を \(0.5\) リットル、果物 \(2\) を \(0.3\) リットル、果物 \(3\) を \(0.2\) リットル混ぜるなどとすることができます。
サンプル5
入力
9 36 459473288 389234620 200824516 103210888 47314058 533584454 391380554 875989889 257188584
出力
10107195609
答えは \(2^{32}\) を超える可能性があることに注意してください。
果物 \(1,2\) をそれぞれ \(7\) リットル、果物 \(3,4,5\) をそれぞれ \(6\) リットル、果物 \(6,7,8,9\) をそれぞれ \(1\) リットル混ぜるのが最適です。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。