URI Online Judge | 2475

Manufacture of Presents

By Gabriel Duarte, UNIFESO BR Brazil

Timelimit: 1

Christmas is coming and Santa Claus needs your help to make the gifts he will give.

This year Santa Claus separated all the presents in a row and assigned to each of them a cost for their preparation, however as we are living a crisis year Noel only managed to hire A helpers and will have to split the gifts between them for manufacturing.

Each helper will be responsible for making some presents and they should be adjacent in the row. But as Noel wants to lower costs he has defined the amount that will be paid to each helper as being the sum of the costs of each gift that he will manufacture times the amount of gifts made.

You will be given the gift list, the total helpers, and the cost of each gift, and you should help Noel find out the least amount that will be paid to make all gifts.

Assuming that Noel has 4 presents with the values {5, 1, 10, 2} and 2 helpers and the division is done as follows:
Helper 1 will manufacture gifts 1, 2 and 3 with the total of: (5 + 1 + 10) * 3 = 48
Helper 2 will manufacture gifts 4 with the total of: (2) * 1 = 2
In this configuration the total to be paid will be 50, but a better configuration would be the helper 1 to keep gifts 1 and 2 and helper 2 with gifts 3 and 4, totaling 36.

Input

The first line contains two integers P and A (1 ≤ P ≤ 10⁴, 1 ≤ A ≤ 500), indicating respectively the total of gifts and the total of available helpers.

Then follows P lines, containing an integer Xi (1 ≤ Xi ≤ 10⁹), indicating the cost of manufacturing the present i.

Output

You should print the lowest cost for the manufacture of all gifts, as described in the text.

Input Sample Output Sample

6 3
10
12
18
26
26
150

374