그래프 만들기

노드 $N$개와 간선 $N-1$개로 이루어진 그래프를 만든다. 이 그래프는 연결되어 있어야 한다.

아래 그림은 노드 $N=5$개와 간선 $N-1=4$개로 이루어진 그래프다.

간선은 두 노드를 연결할 수 있다. 노드의 차수는 그 노드에 연결된 간선의 개수다. 위 그림에서 A의 차수는 3, B의 차수는 1이다.

그래프의 점수는 모든 노드의 점수를 더한 값이고, 각 노드의 점수는 그 노드의 차수만으로 정해진다. 차수별 점수가 주어질 때, 조건을 만족하는 그래프 중 점수가 가장 큰 것의 점수를 구하는 프로그램을 작성하시오.

첫째 줄에 노드의 개수 $N$이 주어진다. ($1 \le N \le 51$)

둘째 줄에 차수별 점수가 $N-1$개 주어진다. 차수가 1인 노드의 점수, 차수가 2인 노드의 점수, ..., 차수가 $N-1$인 노드의 점수 순서다. 각 점수는 0 이상 10,000 이하의 정수다.

$N$이 1이면 둘째 줄은 비어 있다.

첫째 줄에 만들 수 있는 그래프의 점수 중 최댓값을 출력한다.

$N$이 1이면 간선이 없고 차수 0에 대한 점수는 주어지지 않으므로 0을 출력한다.