Spell Cards

마리사는 바닥에 일렬로 늘어놓은 $N$장의 카드로 마법을 연습하고 있다. 왼쪽에서부터 $i$번째에 있는 $i$번 카드의 마력 소모량은 $a\_i$로 표현된다. 마리사가 $i$번 카드에 마법을 사용하기 위해서는 $a\_i$만큼의 마력을 소모해야 한다.

마리사는 인접한 두 카드를 골라서 마법을 시전한다. 이때 마리사는 고른 두 카드의 마력 소모량의 합만큼 마력을 소모한다. 이후 두 카드는 그 자리에서 하나로 합쳐지며, 새로 만들어진 카드의 마력 소모량은 이전 두 카드의 마력 소모량 중 최댓값이 된다. 이 과정은 카드가 단 하나만 남을 때까지 반복한다.

마리사는 소모하는 마력을 최소화하려 한다. 이때 마리사가 소모할 마력의 양을 구해주자!

첫 번째 줄에 카드의 개수 $N$이 주어진다. $(1 \leq N \leq 400)$

두 번째 줄에 카드의 마력 소모량을 나타내는 정수 $a\_1, a\_2, \cdots, a\_N$가 공백으로 구분되어 주어진다. $(1 \leq a\_i \leq 10^9)$

마리사가 소모하는 마력의 최솟값을 출력한다.