题目描述

S工程公司高薪招聘项目经理，应聘的人很多，总经理想从中选一名有真才实学的项目经理，请Hanks博士给他出了一道招聘考试题：

有$\red{n}$根钢管，长短不一，如果把任意两根长为$\red{L1、L2}$的钢管焊为一根，所需时间为$\red{L1+L2}$，现要把所有的钢管焊为一根，应如何安排焊接，使完工的时间最短，并求出最短的完工时间。

输入格式

第一行为一个整数$\red{n（3≤n≤1000）}$，表示有$\red{n}$根钢管。接下来的是$\red{n}$个整数，分别代表$\red{n}$根钢管的长度。你的任务是编程求出将这$\red{n}$根钢管焊为一根所需的最短时间。

输出格式

一个数，最短完工时间。

样例

输入样例

3
1 3 2

输出样例

9