Xếp gạch

Có \(N\) đống gạch được xếp thành một hàng, đống thứ \(i\) có \(a_i\) viên gạch. Ta có thể ghép hai đống gạch kề nhau thành một đống, và mất một chi phí thời gian bằng tổng số viên gạch của hai đống đó. Sau khi ghép, hai đống được thay bằng một đống mới có số viên gạch bằng tổng của chúng.

Yêu cầu: Hãy ghép \(N\) đống gạch thành đúng một đống sao cho tổng chi phí thời gian là lớn nhất.

Input

Dòng đầu chứa số nguyên \(N\) \((2 \le N \le 100)\).

Dòng thứ hai chứa \(N\) số nguyên dương \(a_1,a_2,\ldots,a_N\) \((1 \le a_i \le 1000)\).

Output

In ra một số nguyên duy nhất là tổng chi phí thời gian lớn nhất có thể đạt được.

Scoring

• Subtask 1 (30 points): \(2 \le N \le 30\).
• Subtask 2 (70 points): Không có ràng buộc thêm.

Sample Input 1

4
5 2 8 3

Sample Output 1

43