Misaka is fighting against an enemy army consisting of robots standing in a row, with the robot having a power of . Misaka wants to weaken the enemy army as much as possible by destroying powerful robots, but she can only attack from either the left side or the right side. Fortunately, she has a powerful ability called Railgun that can destroy the leftmost robots or the rightmost robots. If there are fewer than robots left, using the ability will destroy all of them.
After using her Railgun ability at most times, by how much can she weaken the enemy army's power?
Constraints
Subtask 1 [2/15]
The robots are sorted in non-decreasing order in terms of power.
Subtask 2 [9/15]
is divisible by .
Subtask 3 [4/15]
No additional constraints.
Input Specification
The first line of input contains space separated integers, , , and .
The second line of input containts space separated integers, the power of each robot.
Output Specification
Output a positive integer, the sum of the destroyed robots' powers.
Sample Input 1
5 2 1
1 2 3 4 5
Sample Output 1
9
Explanation for Sample Output 1
Misaka can destroy the leftmost robots or the rightmost robots. She can weaken the enemy army more by destroying the rightmost robots .
Sample Input 2
10 2 3
10 1 3 2 9 9 8 9 1 1
Sample Output 2
37
Explanation for Sample Output 2
To attack optimally, Misaka first destroys the rightmost robots.
The robots' powers now become:
Then, she destroys the rightmost robots again.
The robots' powers now become:
Finally, she destroys the rightmost robots one more time.
The robots' powers now become:
In total, she weakened the army by .
Sample Input 3
11 4 2
9 4 1 3 2 1 3 2 9 1 1
Sample Output 3
30
Explanation for Sample Output 3
To attack optimally, Misaka first destroys the rightmost robots.
The robots' powers now become:
Then, she destroys the leftmost robots.
The robots' powers now become:
In total, she weakened the army by .
Sample Input 4
5 4 5
1 1 1 1 1
Sample Output 4
5
Explanation for Sample Output 4
All robots are destroyed no matter how she attacks.
Comments