Description

有 $n$ 堆石子排成一行，每次选择相邻的两堆石子，将其合并为一堆，记录该次合并的得分为两堆石子个数之和。已知每堆石子的石子个数，求当所有石子合并为一堆时，最小的总得分。

Input

第一行一个整数 $n$ ($1 <= n <= 200$)，表示石子堆数； 第二行 $n$ 个整数 $a$ $(1 <= a <= 100)$，表示每堆石子的个数。

Output

一个整数，表示最小总得分。

Samples

5
7 6 5 7 100

175