坤城养鸡场的鸡下蛋了！农场主蔡伯伯可高兴了。为方便存放，他希望将所有鸡的蛋合并成一堆。
养鸡场里共有 只鸡，按顺序排成一排，第 只鸡下了 个蛋。每次操作，将相邻的两只鸡下的蛋合并起来，需要花费的代价为这两只鸡一共下的蛋的个数。
求将所有鸡的蛋合并成一堆组要的最小代价。
输入包含两行。
第一行，包含一个整数 。
第二行，包含 个整数： 。
一行一个整数，即将所有鸡的蛋合并成一堆组要的最小代价。
6 1 1 4 5 1 4
39
6 1 9 1 9 8 10
96
12 1 1 4 5 1 4 1 9 1 9 8 10
181
对于 的数据，保证 。
对于 的数据，保证 ，。
