# d872. 過橋問題
## 題目連結: [d872](https://zerojudge.tw/ShowProblem?problemid=d872)

## 遇到的困難
* 不知道怎麼過才是最佳解
* 不知道要分開討論

## 失敗的程式碼

import sys

for ppl in sys.stdin:
    here = [int(i) for i in input().split()] #橋的這邊
    there = [] #橋的對面
    time = 0

    while len(here) > 0:
        if len(there) <= 0: #如果沒有人在橋的對面
            here.sort()
            try:
                time += here[1]
                there.append(here.pop(0))
                there.append(here.pop(0))
            except:
                time += here[0]
                there.append(here.pop(0))
                break

            if len(here) == 0: break
            
            there.sort()
            print(here," ",there,time,"a")
            time += there[0]
            here.append(there.pop(0))
            print(here," ",there,time,"b")
        else:
            here.sort()
            try:
                there.append(here.pop(-2))
                time += here[-1]
                there.append(here.pop(-1))
            except:
                time += here[0]
                there.append(here.pop(0))
                break

            if len(here) == 0: break
            
            there.sort()
            print(here," ",there,time,"c")
            time += there[0]
            here.append(there.pop(0))
            print(here," ",there,time,"d")
        
    print(time)

## 經過老師解釋後的改良
* 分成兩種可能的情況，再找出最小的
* 剩餘人數小於4的時候也要分開討論

## 程式碼

import sys

for ppl in sys.stdin:
    here = [int(i) for i in input().split()]
    here.sort()
    time = 0

    np = int(ppl)

    while np >= 4:
        #case1 第一快跟第二快過去，第一快回來，最慢兩個再過去
        t1 = here[0]*2 + here[np-2] + here[np-1]
        #case2 如果第二快也很慢，第一快帶最慢過去，並依序帶完所有人
        t2 = here[0] + here[1]*2 +here[np-1]
        time += min(t1,t2)

        np -= 2

    if np == 3:
        time += here[2]+here[0]+here[1]
    elif np == 2:
        time += here[1]
    else:
        time += here[0]

    print(time)
    

如此一來雖然答案都是對的了，但放到[zerohudge](https://zerojudge.tw/)上仍會發生TLE問題