Jailbreak

A prison has $L$ cells in a row. The cells are numbered 1 through $L$, and cell $i$ holds one prisoner. The escape power of the prisoner in cell $i$ is $C_i$, a number that measures how well that prisoner can break out.

The ideal way to watch the prison is to put one guard on every cell, so that each guard watches a single prisoner. Because of the budget, this prison can hire at most $G$ guards. You want to hire and place the guards so that the escape risk is as small as possible.

Each guard watches cells with consecutive numbers, and every cell is watched by exactly one guard. The escape risk $R_i$ of cell $i$ is the escape power $C_i$ multiplied by the number of prisoners watched by the guard in charge of cell $i$. The escape risk of the prison is the sum of $R_i$ over all cells.

Given $L$, $G$, and the escape power $C_i$ of the prisoner in each cell, write a program that finds the minimum escape risk.

The first line contains the size of the prison $L$ and the number of guards $G$, separated by a space. ($1 \le L \le 8000$, $1 \le G \le 800$)

The second line contains $C_1, C_2, \dots, C_L$ separated by spaces. ($1 \le C_i \le 10^9$)

Print the minimum escape risk on the first line.

In the first example the escape risk is smallest when one guard watches cells 1, 2, 3, another guard watches cells 4, 5, and the remaining guard watches cell 6.

The guard in charge of cells 1, 2, 3 watches three prisoners, so the escape risk of each of those cells is $11 \times 3 = 33$.

The guard in charge of cells 4, 5 watches two prisoners, so cell 4 gives $24 \times 2 = 48$ and cell 5 gives $26 \times 2 = 52$.

The guard in charge of cell 6 watches one prisoner, so cell 6 gives $100 \times 1 = 100$. The total is $33 \times 3 + 48 + 52 + 100 = 299$.