WC '15 Contest 1 J3 - Jazz Concert

View as PDF

Points: 5
Time limit: 1.0s
Memory limit: 16M

Authors:
Problem type
Woburn Challenge 2015-16 Round 1 - Junior Division

The renowned Woburn Jazz Band is putting on a concert!

Their current repertoire consists of different songs that are numbered with distinct integers from to . The -th of these songs (for ) has a duration of minutes.

Since the band is so spectacular, they are always receiving requests to fill more and more time. Unfortunately, rehearsal times are tight and practicing any more than these pieces is simply not feasible. Through Mr. Farrow's decades of experience as conductor of the band, he has observed that they can always get away with repeating at most two of their songs to extend the concert (surely the audience won't notice). With that in mind, the band has decided to pick two songs to play twice, while each of the remaining songs will be played exactly once. Furthermore, there will always be a -minute intermission in the middle of the concert.

With all this information, Mr. Farrow needs to know ahead of time the length of the entire concert so that he can report it to the principal for scheduling purposes. Given the lengths of all the pieces in the Jazz Band's repertoire, please help Mr. Farrow determine the maximum amount of time (in minutes) that the concert could possibly last, including the intermission time and given that optimal choices will be made for which two songs are to be repeated.

Input Specification

Line of input will contain a single integer , representing the number of songs in the band's repertoire.
lines will follow, with the -th of these lines (for ) containing a single integer , representing the duration of the -th song in minutes.

Output Specification

Output a single integer representing the maximum possible length of the concert in minutes.

Sample Input

4
10
10
20
25

Sample Output

120