Problem M
Marvelous Marathon
A marathon race is being planned in the beautiful countryside. The course will be somewhere along a long, bidirectional, road. The organizers want to determine exactly where along this road the race should be in order to maximize the experience for the runners, so that they get to enjoy as much beautiful scenery as possible and are distracted from their tired limbs. The scenery varies in beauty depending on where on the road you are, and also in which direction you are running. Because of this, the organizers are fine with having the runners make up to two U-turns, as long as no part of the road is used more than once in each direction.
We model the road of length
The road is long, so rather than providing a list of all of
the
![\includegraphics[width=0.95\textwidth ]{sample1.pdf}](/problems/marvelousmarathon/file/statement/en/img-0001.png)
Input
The first line of input contains the three integers
This is followed by
The parts of the road that are not covered by any segments
have beauty value
Output
Output the maximum possible total beauty the race can have.
Sample Input 1 | Sample Output 1 |
---|---|
19 14 6 14 5 7 11 15 6 3 7 4 16 15 5 19 17 8 0 3 9 |
89 |
Sample Input 2 | Sample Output 2 |
---|---|
100000 42195 2 30000 60000 500000000 40000 10000 1000000000 |
35548500000000 |