안전한 귀환

학생 여러 명이 몰래 학교 밖으로 빠져나갔다가, 이제 정문에서 기숙사까지 돌아가야 한다. 캠퍼스를 순찰하는 교사가 많아서 들키면 안 된다. 다행히 투명 망토가 하나 있지만, 한 번에 두 명까지만 덮을 수 있다.

학생들은 혼자 또는 두 명씩 망토를 쓰고 정문에서 기숙사로 이동한다. 정문에 아직 남은 학생이 있으면 기숙사에 도착한 학생 중 한 명이 망토를 들고 정문으로 되돌아와야 한다. 학생마다 캠퍼스를 혼자 건너는 데 걸리는 시간이 정해져 있고, 두 명이 함께 망토를 쓰면 둘 중 느린 쪽의 시간이 걸린다.

모두가 기숙사에 도착할 때까지 걸리는 시간을 최소로 만들어야 한다.

예를 들어 네 명이 있고 A는 1분, B는 2분, C는 7분, D는 10분에 캠퍼스를 건넌다고 하자. 다음 순서를 따르면 17분 만에 모두 기숙사에 도착한다.

• A와 B가 함께 기숙사로 간다 (2분)
• A가 망토를 들고 정문으로 돌아온다 (1분)
• C와 D가 함께 기숙사로 간다 (10분)
• B가 망토를 들고 정문으로 돌아온다 (2분)
• A와 B가 함께 기숙사로 간다 (2분)

입력은 한 줄이다. 첫 번째 정수는 학생 수 $N$이고, $2 \le N \le 15$이다. 이어서 각 학생이 혼자 캠퍼스를 건너는 데 걸리는 최소 시간을 나타내는 양의 정수 $N$개가 주어진다. 단위는 분이고, 각 값은 $5000$ 이하이다. 캠퍼스가 아주 넓기 때문이다.

모든 학생이 정문에서 기숙사까지 이동하는 데 걸리는 최소 시간을 출력한다.