시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 1024 MB 101 49 39 52.703%

문제

세 모질이들 관우, 철환, 길원이가 모였다. 모질이들은 모이면 서로 '햄버거 최대 몇 개 드실 수 있나요?'의 준말인 '햄최몇?'을 시전하며 자랑을 하기 바쁘다.

막내 길원이는 문득 중요한 사실을 깨달았다. 바로, 개수가 중요한 것이 아니라 최대 효용이 중요하다는 것이었다! 이들은 바로 N개의 햄버거를 준비했다. 그리고 이 햄버거를 사이좋게 나누어 먹었다. 각 모질이들이 얻을 수 있는 효용은 이들이 먹은 햄버거들의 효용의 합이다. 또한 나름의 서열과 규칙이 있어, 존경하는 선배님들보다는 높은 효용을 누려서는 안 된다.

막내 길원이는 선배님들을 존경하기 때문에 규칙을 따라야 하는 한편, 햄버거를 잘 분배하여 본인이 얻을 수 있는 효용이 최대가 되도록 하고 싶다.

입력

첫 번째 줄에 (1 ≤ ≤ 50)이 주어진다. N은 햄버거의 수이다.

두 번째 줄에 N개의 양의 정수 ai (1 ≤ ai ≤ 50)가 공백으로 구분되어 주어진다. 각각의 값은 햄버거의 효용을 의미한다.

출력

세 모질이 중 막내 길원이가 얻을 수 있는 효용의 합의 최댓값을 출력한다.

예제 입력 1

10
4 37 50 2 6 15 2 13 3 10

예제 출력 1

46