問題文
东京小太郎君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
- 13 个整数在线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