You are given an array $A$ of $n$ integers. Merging 2 adjacent elements $A_i$ and $A_{i + 1}$ costs $A_i + A_{i + 1}$.

Perform the above operation until there is only $1$ element left in $A$, what is the minimum cost?

Input

• The first line contains an integers $n$.
• The second line contains $n$ integers $A_i$.

Output

• Print the minimum cost.

Constraints

• $1 \le n \le 500$.
• $1 \le A_i \le 10^9$.

Example

Input:

4
10 20 30 40

Output:

190

The merging happens as follows (bolded elements are merged elements):

• (10, 20, 30, 40) → (30, 30, 40)
• (30, 30, 40) → (60, 40)
• (60, 40) → (100)