6009 - 过河问题
Time Limit : 1 秒
Memory Limit : 64 MB
有n个人要渡河，但只有一条小船，这条小船一次只能坐下最多两个人，并且只有一副船桨。每个人划船的速度不一样，如果两个人一起上船，由于重量变大，划船的速度基本上相当于是划船速度最慢的那个人速度。假设给出每个人单独划船过河所花费的时间T_i，请问所有人都过河的总时间最短的时间
Input
输入两行
第一行是一个整数，表示要过河的n个人
第二行是n个空格隔开的整数，按速度从快到慢排序好的每个人划船过河的时间
Output
一行，所有人过河所花费最短的时间
Examples
Input
3 1 2 3
Output
6
Input
4 1 2 5 10
Output
17
Source
2024安徽省信息素养复赛智能算法挑战赛