题目描述

有一排石子，每次只能合并相邻两堆，代价为两堆石子数之和。求合成一堆的最小总代价。

输入格式

第一行 $n$，第二行各堆数量。

输出格式

输出最小总代价。

样例

4
1 3 5 2

22

数据规模与约定

$1\le n\le300$。