Problem : 61 - 獨木橋

Problem Statistics

Solved Member: 26　　Submission: 101　　User Tried: 27

Statement:

你玩過Family Crisis這個小遊戲嗎？

遊戲規則是這樣的，有n個人排隊要過一座橋，每一個人有它自己過橋所需要花的時間。剛開始每一個人都在橋的右邊，最終的目的是讓所有人移動到橋的左邊。

他們只有一盞燈，剛開始燈也在右邊，因為橋太暗了所以過橋的時候必須要提燈，否則很容易跌落山谷。獨木橋最多只可以同時讓兩個人一起行走，當兩個人一起行走的時候時間以比較慢的那個人為準(例如3 5一起走，過橋的時間為5)。

現在給你n個人，以及n個人單獨過橋所需要的時間，請問你是否能夠找出最短的時間使大家都平安渡到對面?

Input:Output:

第1行有一個整數N($1 \leq N \leq 100000$)，代表有N個人要過橋。
第2行有N個整數，每個整數分別代表其中一個人單獨要過橋所需要花的時間，其中過橋時間必定<=1000。

輸出一行數字，代表全員過橋所需的最短時間。

Sample Input:Sample Output:

5
1 3 6 8 12

HINT:

範例測資為遊戲中的情況，最短時間為29。

Source:

UVA 10037

Problem Setter

Nekosyndrome

Testdata:

Test	Time	Memory	Score
0	500ms	32768kb
1-1	500ms	32768kb	10
1-2	500ms	32768kb
2-1	500ms	32768kb	10
2-2	500ms	32768kb
3-1	500ms	32768kb	10
3-2	500ms	32768kb
3-3	500ms	32768kb
4-1	500ms	32768kb	10
4-2	500ms	32768kb
5-1	500ms	32768kb	10
5-2	500ms	32768kb
6	500ms	32768kb	10
7	500ms	32768kb	10
8	500ms	32768kb	10
9	500ms	32768kb	10
10	500ms	32768kb	10