다리 건너기

깊은 밤, 한 무리의 관광객이 낡고 무너져 가는 다리를 건너려고 합니다. 이들에게는 손전등이 하나뿐입니다. 손전등이 있어야 다리를 건널 수 있고, 한 번에 최대 두 명까지만 함께 건널 수 있습니다. 손전등 없이 건너거나 세 명 이상이 한꺼번에 건너면 강에 빠지고 맙니다. 각 관광객은 다리를 건너는 데 저마다 일정한 시간이 필요합니다. 두 사람이 함께 건널 때는 더 느린 사람의 속도에 맞추므로, 두 사람 중 더 오래 걸리는 사람의 시간만큼 걸립니다. 모든 관광객이 다리를 건너는 데 걸리는 가장 짧은 시간은 얼마일까요?

예를 들어 관광객이 4명이고 다리를 건너는 데 각각 6분, 7분, 10분, 15분이 걸린다고 합시다. 아래 그림은 이들이 44분 만에 건너는 한 가지 방법을 보여 줍니다. 하지만 실제로는 더 빠르게 건널 수도 있습니다.

44분 만에 다리를 건너는 한 가지 방법. 각 원 안의 숫자는 그 관광객이 다리를 건너는 데 필요한 시간(분)입니다.

다음을 수행하는 프로그램을 작성하세요.

• 표준 입력에서 관광객 무리에 대한 정보를 읽고,
• 모두가 다리를 건너는 데 필요한 가장 짧은 시간을 구하여,
• 그 결과를 표준 출력에 씁니다.

첫째 줄에 관광객의 수를 나타내는 양의 정수 $n$이 주어집니다 ($1 \le n \le 100000$). 이어지는 $n$개의 줄에는 각 줄마다 정수가 하나씩 주어지며, $i$번째 줄의 수는 $i$번째 관광객이 다리를 건너는 데 필요한 시간입니다. 이 시간들은 감소하지 않는 순서(오름차순)로 주어지고, 각 값은 $10^9$ 이하이며, 모든 값의 합은 $10^9$을 넘지 않습니다.

모든 관광객이 다리를 건너는 데 필요한 가장 짧은 시간을 정수 하나로 출력합니다.