节省时间2

题目描述

童程学校的信息奥赛课非常受欢迎，每次午休，学生们都要排队找老师答疑。学校看到人山人海的学生，由原来1位老师增加到2位老师。

由于每位同学的答疑时间可能不同，学校想知道如何排队才能使学生总答疑完成时间最少。注意：每个学生的答疑完成时间=自己的答疑时间+等前面同学的时间。

输入格式

第一行 n表示学生人数（$n \le 400$）。

第二行n个整数，表示每位同学的答疑时间 $t_i$（$t_i \le 30$）。

输出格式

最少的总答疑时间。

样例输入 #1

4
2 3 1 2

样例输出 #1

11

数据范围

$n \le 400$，$t_i \le 30$。

知识点与难度

本题涉及的知识点从属于 GESP五级（贪心基础），难度等级：⭐⭐。

测试点分布