Building a Graph

Time limit2sMemory limit512 MB

Summary

Build a connected graph (tree) with N nodes and N-1 edges, where each node's score depends on its degree, and maximize the total score.

Level: Medium6 of 10
Topics: Tree, Dynamic programming, Combinatorics
Solved: No attempts yet

Problem

You build a graph with $N$ nodes and $N-1$ edges. The graph must be connected.

The figure below is a graph with $N=5$ nodes and $N-1=4$ edges.

An edge can connect two nodes. The degree of a node is the number of edges attached to it. In the figure above, A has degree 3 and B has degree 1.

The score of the graph is the sum of the scores of all nodes, and the score of a node is decided by its degree alone. Given the score for each degree, write a program that finds the largest score among the graphs that meet the conditions.

Input

The first line contains the number of nodes $N$ . ( $1 \le N \le 51$ )

The second line contains $N-1$ scores by degree: the score of a node of degree 1, the score of a node of degree 2, ..., the score of a node of degree $N-1$ , in that order. Each score is an integer between 0 and 10,000.

If $N$ is 1, the second line is empty.

Output

Print the largest score among the graphs you can build.

If $N$ is 1, there are no edges and no score is given for degree 0, so print 0.

Examples5

Example 1
Input
```
4
1 3 0
```
Expected output
```
8
```
Example 2
Input
```
5
0 0 0 10
```
Expected output
```
10
```
Example 3
Input
```
7
1 2 3 4 5 6
```
Expected output
```
12
```
Example 4
Input
```
4
5 0 0
```
Expected output
```
15
```
Example 5
Input
```
8
1 3 2 5 3 7 5
```
Expected output
```
20
```