题目描述

HY在回家的途中遇到了一棵树，这棵树有 $n$ 个节点，但却缺少 $n-1$ 条边。HY想在这棵树下乘凉，而HY很懒，现在希望你帮助他来完成这棵树。

你需要添加 $n-1$ 条边来完成这棵树，添加后，任意两个节点之间必须只有一条路径(满足树的定义)。HY希望这棵树的凉爽度尽可能的大。已知一棵树的凉爽度是其节点凉爽度的总和。

节点的凉爽度为 $f(d)$ ，其中 $d$ 为节点的度数。完成树的最大凉爽度是什么？

Tips:每棵树有 $n$ 个节点的树有 $2\times n-2$ 个度(即每个边产生一个入度和出度)。

输入格式

每个文件包含一组测试样例

测试样例以一个整数 $n$ 开头，第二行有 $n-1$ 个整数 $f(1),f(2),\dots,f(n-1)$ ，分别表示度数为 $1$ 到 $n-1$ 的节点的凉爽度。 $2\le n\le 4015,0\le f(i)\le 10000$

对于每组测试样例，请在一行中输出完成树的最大凉爽度。

3
2 1

4
5 1 4