Problem Description

Taro Kogaku-kun eats one bowl of tantanmen (spicy noodle) every day for \( N \) days. He can put any amount of la-yu (spicy chili oil) on the tantanmen. When Taro eats tantanmen with \( x_i \) la-yu on the \( i \)-th day (\( 1 \leq i \leq N \)), he gains a happiness score of \( A_i \ x_i \).

Taro has a sensitive stomach, so he needs to satisfy \( 0 \leq x_i \leq B \) (\( 1 \leq i \leq N \)) and \( \Sigma_{1 \leq i \leq N} x_i \leq C \). Also, la-yu is very delicious, so when \( N \geq 2 \), for any \( i \) (\( 1 \leq i \leq N-1 \)), \( A_i \leq A_{i+1} \) holds.

Find the maximum sum of happiness scores Taro can gain over \( N \) days.

Input Format

The input is given from the standard input in the following format:

\( N \) \( B \) \( C \) \( A_1 \) \( ... \) \( A_N \)

• The first line contains three integers \( N \) (\( 1 \leq N \leq 100 \)), \( B \) (\( 1 \leq B \leq 10000 \)), \( C \) (\( 1 \leq C \leq 10000 \)) separated by spaces.
• The second line contains \( N \) integers \( A_1, ..., A_N \) (\( 0 \leq A_i \leq 100 \)) separated by spaces.
• When \( N \geq 2 \), for any \( i \) (\( 1 \leq i \leq N-1 \)), \( A_i \leq A_{i+1} \).

Output Format

Output the maximum sum of happiness scores Taro can gain over \( N \) days in one line. End the output with a newline.

Sample Input and Output

Sample Input #1

3 2 5
1 2 3

Sample Output #1

11

Sample Input #2

3 100 100
1 2 100

Sample Output #2

10000

Sample Input #3

5 0 10000
1 2 3 7 15

Sample Output #3

0

Sample Input #4

6 10000 0
1 2 4 8 16 97

Sample Output #4

0

Sample Input #5

5 10000 10000
0 0 0 0 0

Sample Output #5

0

Sample Input #6

8 5 32
0 1 1 2 3 5 8 13

Sample Output #6

162

Notes/Hints

Sample Explanation 1

The optimal strategy is to put 1 unit of la-yu on the first day and 2 units on the second and third days, making Taro 11 units happier.

Sample Explanation 2

The optimal strategy is to put no la-yu on the first and second days and 100 units on the third day, making Taro 10000 units happier.

Sample Explanation 3

Taro does not add any extra la-yu.

Sample Explanation 4

Taro's stomach is very sensitive, so he cannot add any extra la-yu.

Sample Explanation 5

No matter how much la-yu is added, Taro cannot become happier.

见题面 Input 部分

见题面 Output 部分