B - ラー油
解説
/
実行時間制限: 2 sec / メモリ制限: 256 MB
問題文
東工太郎君はN日間、毎日1食担々麺を食べます。 担々麺には好きな量のラー油をかけることが出来ます。 太郎君がi日目(1 \leq i \leq N)にラー油をx_iかけた担々麺を食べた時、 幸福度をA_i x_i得ることが出来ます。
太郎君はおなかが弱いので、0 \leq x_i \leq B \, (1 \leq i \leq N)かつ\Σ_{1 \leq i \leq N} x_i \leq Cである必要があります。 また、ラー油はとてもおいしいのでN \geq 2のとき任意のi(1 \leq i \leq N-1)に対してA_i \leq A_{i+1}が成り立ちます。
太郎君が得られるN日間の幸福度の和の最大値を求めてください。
入力
入力は以下の形式で標準入力から与えられる。
N B C A_1 ... A_N
- 1行目に3つの整数N(1 \leq N \leq 100) , \, B(1 \leq B \leq 10000), \, C(1 \leq C \leq 10000)が空白区切りで与えられる。
- 2行目にN個の整数A_1, …, A_N (0 \leq A_i \leq 100)が空白区切りで与えられる。
- N \geq 2のとき任意のi(1 \leq i \leq N-1)に対してA_i \leq A_{i+1}
出力
太郎君が得られるN日間の幸福度の和の最大値を1行に出力してください。出力の末尾に改行を入れること。
入力例1
3 2 5 1 2 3
出力例1
11
1日目に1だけラー油をかけ、2日目と3日目に2だけラー油をかけるのが最適であり、太郎君は11だけ幸せになれます。
入力例2
3 100 100 1 2 100
出力例2
10000
1日目と2日目にはラー油をかけず3日目に100だけラー油をかけるのが最適であり、太郎君は10000だけ幸せになれます。
入力例3
5 0 10000 1 2 3 7 15
出力例3
0
太郎君は追加でラー油をかけることはない。
入力例4
6 10000 0 1 2 4 8 16 97
出力例4
0
太郎君のおなかはとても弱いので追加でラー油をかけることはできない。
入力例5
5 10000 10000 0 0 0 0 0
出力例5
0
ラー油をどれだけかけても幸せにはなれない。
入力例6
8 5 32 0 1 1 2 3 5 8 13
出力例6
162