다리 건너기

n명이 밤에 다리를 건너려고 합니다. 한 번에 최대 두 명까지 함께 건널 수 있으며, 건너는 무리는 반드시 손전등을 가지고 있어야 합니다. 손전등은 단 하나뿐이므로, 한 무리가 건넌 뒤에는 누군가가 손전등을 다시 가지고 돌아와야 남은 사람들이 건널 수 있습니다.

사람마다 다리를 건너는 속도가 서로 다를 수 있습니다. 두 사람이 함께 건널 때 그 무리에 걸리는 시간은 더 느린 사람에게 걸리는 시간과 같습니다. n명 모두가 다리를 건너는 데 필요한 최소 시간을 구하세요.

첫째 줄에 사람 수 n이 주어집니다. 이어지는 n개의 줄에는 각 사람이 다리를 건너는 데 걸리는 시간이 한 줄에 하나씩 주어집니다.

사람은 최대 1000명이며, 한 사람이 다리를 건너는 데 걸리는 시간은 100초를 넘지 않습니다.

n명 모두가 다리를 건너는 데 필요한 최소 시간(초)을 정수 하나로 출력하세요.