Building a Graph

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.

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.

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.