Cheapest version merge: hints, no solution

A document store keeps a row of versions, where sizes[i] is the size in kilobytes of version i. In one step you may merge two neighbouring versions into a single version whose size is the sum of the two, and that step costs the combined size. Only versions that are neighbours in the current row can be merged. Merge the whole row down to a single version and return the minimum total cost. A row with one version costs 0. Aim for O(n^3) time: trying every merge order, or always merging the cheapest pair, will not pass.

Examples

Input

sizes = [6, 4, 4, 6]

Output

40

Note

Merge the outer pairs (10 and 10) then the two results (20). Merging the two 4s first costs 42.

Input

sizes = [5]

Output

0

Note

A single version needs no merging.

Input

sizes = [2, 3, 1]

Output

10

Note

Merge 3 and 1 for 4, then 2 and 4 for 6.

Constraints

• 1 <= sizes.length <= 250
• 1 <= sizes[i] <= 1000
• The answer fits in a 32-bit signed integer

Hint 1: a nudge

Look at the very last merge, the one that produces the whole row. It joins a left group with a right group. What do you know about how each group was built?

Unlock the full hints and timed practice with a pass

The second and third hints and the timed, runner-checked practice are part of a pass.

See pricing