카드 합성 이벤트

영관이는 모바일 보드게임의 카드 합성 이벤트에 참여했다.

이벤트에는 순서가 정해진 카드 $n$장이 한 줄로 놓여 있고, 카드마다 레벨이 하나씩 적혀 있다.

카드 A에 카드 B를 덧붙여 한 장으로 합칠 수 있다. 조건은 다음과 같다.

1. 두 카드는 줄에서 서로 인접해야 한다.
2. 합친 카드의 레벨은 A의 레벨과 같다. 덧붙인 B의 레벨은 사라진다.
3. 합친 카드는 두 카드가 있던 자리에 그대로 남고, 다음 합성에서 한 장의 카드로 쓰인다.

합성을 한 번 할 때마다 합치기 직전 두 카드의 레벨을 더한 만큼 골드를 받는다.

카드가 한 장만 남을 때까지 합성을 $n-1$번 한다. 영관이가 받을 수 있는 골드의 최댓값을 구해라.

레벨이 40, 30, 30인 카드 세 장 $c_1, c_2, c_3$으로 규칙을 확인해 보자. $c_3$에 $c_2$를 덧붙이면 레벨 30인 카드가 남고 골드 60을 받는다. 이어서 $c_1$에 그 카드를 덧붙이면 레벨 40인 카드가 남고 골드 70을 받아 합계는 130이다. 순서를 바꿔 $c_1$에 $c_2$를 덧붙이면 레벨 40인 카드가 남고 골드 70을 받는다. 그 카드에 $c_3$을 덧붙이면 골드 70을 다시 받아 합계는 140이다.

첫째 줄에 카드의 개수 $n$이 주어진다. ($1 \le n \le 1000$)

둘째 줄에 카드 $n$장의 레벨 $L_1, L_2, \dots, L_n$이 놓인 순서대로 주어진다. ($0 < L_i \le 100000$)

받을 수 있는 골드의 최댓값을 한 줄에 출력한다. $n = 1$이면 합성을 하지 않으므로 0을 출력한다.