题目描述

童程学校的信息奥赛课非常受欢迎，每次午休，学生们都要排队找老师答疑。学校由原来 1 位老师增加到 2 位老师。由于每位同学的答疑时间可能不同，学校想知道如何排队才能使学生总答疑完成时间最少。

注意：每个学生的答疑完成时间 = 自己的答疑时间 + 等前面同学的时间。

输入格式

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

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

输出格式

一行，一个整数，表示最少的总答疑时间。

样例

4
2 3 1 2

11

说明/提示

答疑时间短的同学先答疑，可以让后面所有人等待的时间更短。将答疑时间升序排序后，第 1、2 位同学分别是两位老师队列中的第一位；从第 3 位同学开始，他的答疑完成时间 = 自己的答疑时间 + 前面隔一位（同队列前一位）同学的答疑完成时间。