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
Comments