j02020. 夜行过桥 未做

夜晚 $n$ 人要过一座桥。每次过桥至多 2 人且必须带手电筒，全队只有一盏手电，过桥后须由过桥的人把手电送回。第 $i$ 人单独过桥需 $t_i$ 分钟，两人同行耗时为较慢者。求 $n$ 人全部过桥的最短总时间。

第一行 $n$；第二行 $t_1$..$t_n$。

一个整数，最短总时间。

• 30% $n$$\le$3（可直接枚举过桥顺序）。
• 60% $n$$\le$$1\times 10^3$。
• 100% $n$$\le$$1\times 10^5$，1$\le$$t_i$$\le$$1\times 10^6$（答案需 long long）。