问题描述

xwj的信奥赛课非常受欢迎，每次午休，同学们都要排队找老师答疑。学校看到人山人海的学生，由原来1位老师增加到2位老师。 由于每位同学的答疑时间可能不同，学校想知道如何排队才能使学生总答疑完成时间最少。 注意:每个学生的答疑完成时间=自己的答疑时间+等前面同学的时间。

输入格式

第一行 n表示学生人数(n≤40000) 第二行n个整数，表示每位同学的答疑时间 ti(ti≤30)。

输出格式

最少的总答疑时间。

样例输入输出

 4
 2 3 1 2

11