PEG Judge - WC15 #1 - Jazz Concert

Woburn Challenge 2015-16 Round 1 - Junior Division

Problem 3: Jazz Concert

The renowned Woburn Jazz Band is putting on a concert!

Their current repertoire consists of N (2 ≤ N ≤ 100) different songs that are numbered with distinct integers from 1 to N. The i-th of these songs (for i = 1..N) has a duration of T_i (1 ≤ T_i ≤ 100) 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 N 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 N 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 N − 2 remaining songs will be played exactly once. Furthermore, there will always be a 10-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 Format

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