← 返回题目列表

AtCoder · ttpc2015_b

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
  • 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