# Pku1738 An old Stone Game

时间限制：20s 空间限制：64MB

### 题目描述

There is an old stone game. At the beginning of the game the player picks n(1<=n<=50000) piles of stones in a line. The goal is to merge the stones in one pile observing the following rules: At each step of the game,the player can merge two adjoining piles to a new pile.The score is the number of stones in the new pile. You are to write a program to determine the minimum of the total score. 就是最简单的石子合并问题.

### 输入格式

The input contains several test cases. The first line of each test case contains an integer n(N等于100) denoting the number of piles. The following n integers describe the number of stones in each pile at the beginning of the game. The last test case is followed by one zero.

### 输出格式

For each test case output the answer on a single line. You may assume the answer will not exceed 1000000000.

### 样例输入

1 100 3 3 4 3 4 1 1 1 1 0

### 样例输出

0 17 8

### 提示

没有写明提示

### 题目来源

LTC男人八题系列