Problem Statement

Given an integer array A of size N. You have to merge all the elements of the array into one with the minimum possible cost.

The rule for merging is as follows:

• Choose any two adjacent elements of the array with values say X and Y and merge them into a single element with value (X + Y) paying a total cost of (X + Y).

Return the minimum possible cost of merging all elements.

Problem Constraints

1 <= N <= 200

1 <= A[i] <= 103

Input Format

First and only argument is an integer array A of size N.

Output Format

Return an integer denoting the minimum cost of merging all elements.

Example Input

Input 1:

 A = [1, 3, 7]

Input 2:

 A = [1, 2, 3, 4]

Example Output

Output 1:

 15