PIPI和小伙伴们玩起了堆石子的游戏，现在有n堆石子按照环形摆放，PIPI想要将这些石子有序地合并成一堆，将石子合并后会获得相应的分数。

PIPI每次只能选相邻的两堆合并成新的一堆，并将新的一堆的石子数记做该次合并的得分。

现在PIPI想知道有没有这样一种方案，可以使得进行n-1次合并后的总得分是所有方案中最少的呢？

第一行包含整数 n，表示共有n堆石子。

第二行包含n个整数m，分别表示每堆石子的数量。

1<=n<=200,1<=m<=1e5

输出有一行，为所有方案中的最小得分。