Bolinhos de Queijo
Laurêncio adora bolinhos de queijo. Ele possui $$n$$ bolinhos de queijo em um prato, cada um com um valor $$a_i$$. Antes de comê-los, deseja juntá-los até que virem um bolinho só. Para juntar bolinhos de queijo, Laurêncio pode realizar a seguinte operação:
- Escolher dois bolinhos de queijo consecutivos e juntá-los, formando um novo bolinho de queijo que ocupa a posição dos dois bolinhos anteriores. O novo bolinho possuirá valor $$x+y$$, onde $$x$$ e $$y$$ são os valores dos bolinhos originais. Além disso, a operação possui custo de $$x+y$$.
Laurêncio deseja descobrir o menor custo possível para juntar os $$n$$ bolinhos em só. Ajude-o nesta missão!
Entrada
A primeira linha consiste de um inteiro $$n$$.
A segunda linha de entrada possui os valores $$a_i$$ $$(1 \leq i \leq n)$$ dos bolinhos.
Saída
Imprima apenas um inteiro: A menor soma de custos de operações para juntar todos os bolinhos em um só.
Restrições
- $$1 \leq N \leq 400$$
- $$1 \leq a_i \leq 10^9$$
Exemplos:
ENTRADA |
SAÍDA |
4 10 20 30 40 |
190 |
Explicação do caso: Laurêncio pode juntar os bolinhos da seguinte forma:
(10 20 30 40) $$\implies$$ (30 30 40)
(30 30 40) $$\implies$$ (60 40)
(60 40) $$\implies$$ (100)