带权重的石子合并问题

Question

问题：
有N堆石子，每次将相邻两堆合并，合并代价为：

左侧石子堆的石子数a+右侧石子堆的石子数b

求将石子合成一堆的最小代价。

输入
第一行，三个整数N、a、b，用空格分隔。

第二行，N个整数，用空格分隔。

输出
一行，一个整数，为最小代价。

规模
1<=N<=500

1<=a, b<=1000

每堆石子的数量>=0

总石子数不超过1e8

对60%的数据，有a=b

示例
输入：
5 1 1
1 1 1 1 1
输出：
12