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