6009 - 过河问题

通过次数

0

提交次数

0

时间限制 : 1 秒
内存限制 : 64 MB

有n个人要渡河,但只有一条小船,这条小船一次只能坐下最多两个人,并且只有一副船桨。每个人划船的速度不一样,如果两个人一起上船,由于重量变大,划船的速度基本上相当于是划船速度最慢的那个人速度。假设给出每个人单独划船过河所花费的时间T_i,请问所有人都过河的总时间最短的时间

输入

输入两行
第一行是一个整数,表示要过河的n个人
第二行是n个空格隔开的整数,按速度从快到慢排序好的每个人划船过河的时间

输出

一行,所有人过河所花费最短的时间

样例

输入

3
1
2
3

输出

6

输入

4
1
2
5
10

输出

17

来源

2024安徽省信息素养复赛智能算法挑战赛