Problem Description

One day, sanada was told by kaage to draw $ N $ cards.
sanada drew the cards as instructed.
Each card has a number on both the front and the back, and the sum of the numbers on both sides is always $ M $. Among the $ N $ cards drawn by sanada, the number on the front of the $ i $-th card is $ A_i $.

Next, kaage instructed to perform the following operation any number of times within $ K $ times (including 0 times):

• Choose any integers $ x, y $ that satisfy $1 \leq x \leq y \leq N$, and flip all cards from the $ x $-th to the $ y $-th.

Suspicious, sanada sent a spy to kaage's house and learned that the more the sum of the numbers on the front of the $ N $ cards, the more kaage has to study.
For sanada who wants to make kaage study, determine the maximum sum of the numbers on the front of all cards that can be achieved by performing the appropriate number of operations.

Input Format

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

$ N $ $ M $ $ K $
$ A_1 $ $ A_2 $ $\ldots$ $ A_N $

Output Format

Output the maximum sum of the numbers on the front of all cards when the appropriate number of operations is performed.

Sample Input and Output

Sample Input #1

3 6 13 3 4

Sample Output #1

10

Sample Input #2

8 9 21 3 8 7 5 3 5 1

Sample Output #2

52

Notes/Hints

Constraints

• All inputs are integers.
• $1 \leq N \leq 10^6$
• $0 \leq K \leq N$
• $1 \leq M \leq 10^9$
• $1 \leq A_i \leq M-1$

Subtasks

This task has 3 subtasks:

1. (400 points) $N \leq 2000$
2. (400 points) $N \leq 10^5$
3. (300 points) No additional constraints.

Note

When submitting code targeting only subtask 1, it is recommended to add a process that terminates immediately if $ N $ is greater than 2000.

Sample Explanation 1

In this case, the maximum sum of $ 10 $ can be achieved by performing no operations at all.

Sample Explanation 2

For example, by choosing the following intervals for operations, the maximum value of $ 52 $ can be achieved:
- First operation: Flip the cards from the 1st to the 5th. The arrangement of the cards after the operation is {$ 8, 6, 1, 2, 4, 3, 5, 1 $}.
- Second operation: Flip the cards from the 3rd to the 8th. The arrangement of the cards after the operation is {$ 8, 6, 8, 7, 5, 6, 4, 8 $}.

见题面 Input 部分

见题面 Output 部分