408791: GYM103317 G Circus Mayhem

Mei and Kylie are bored at the circus, and decided they wanted to play with fire while Azuko was gone. There are $$$n$$$ flames currently in a line, and each flame has a size $$$s_i$$$. Mei and Kylie want to combine all the flames into 1, but since they aren't fire-benders, it costs a certain amount of energy to merge flames. Given two flames next to each other in line $$$s_i$$$ and $$$s_j$$$, it costs $$$s_i + s_j$$$ to merge the two flames, and then it is replaced with a flame that is $$$s_i + s_j$$$ in size at the same place in line.

Given $$$n$$$ flames and their sizes, determine the minimum cost to merge all the flames!

The first line will contain $$$n$$$ $$$(1 \le n \le 200)$$$, the total number of flames.

The next line will each contain $$$n$$$ integers $$$s_i$$$ $$$(1 \le s_i \le 10^5)$$$, the size of the $$$i^{th}$$$ flame.

A single integer detailing the minimum cost to merge all the flames together into one big flame.

3
1 4 5

15

2
10 9

19