AT_ttpc2015_b ラー油

[problemUrl]: https://atcoder.jp/contests/ttpc2015/tasks/ttpc2015_b 東工太郎君は$ 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 $行に出力してください。出力の末尾に改行を入れること。

### Sample Explanation 1 $ 1 $日目に$ 1 $だけラー油をかけ、$ 2 $日目と$ 3 $日目に$ 2 $だけラー油をかけるのが最適であり、太郎君は$ 11 $だけ幸せになれます。 ### Sample Explanation 2 $ 1 $日目と$ 2 $日目にはラー油をかけず$ 3 $日目に$ 100 $だけラー油をかけるのが最適であり、太郎君は$ 10000 $だけ幸せになれます。 ### Sample Explanation 3 太郎君は追加でラー油をかけることはない。 ### Sample Explanation 4 太郎君のおなかはとても弱いので追加でラー油をかけることはできない。 ### Sample Explanation 5 ラー油をどれだけかけても幸せにはなれない。