B - ラー油 Editorial /

Time Limit: 2 sec / Memory Limit: 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