409425: GYM103536 A Guards

There are $$$N$$$ prisoners in jail cells numbered from $$$0$$$ to $$$N-1$$$ and $$$G$$$ guards. The guards ensure the prisoners do not escape and can only take charge of adjacent segments of jail cells. Each jail cell is assigned to exactly one guard.

Each prisoner $$$i$$$ has a certain intelligence $$$S_i$$$, and if the guard is watching him has $$$k$$$ people to watch over, his escaping possibility will be $$$kS_i$$$. You should assign the guards so that the total escaping possibility over all the prisoners is minimized.

The first line of input contains $$$2$$$ integers $$$N$$$ and $$$G$$$ ($$$1 \leq 8000 \leq N,1 \leq 3000 \leq G$$$).

The next $$$N$$$ lines of input will contain one integer each, $$$S_i$$$ ($$$1 \leq S_i \leq 10^9$$$).

The output should contain one line with one integer, the minimum total escaping possibility.

6 3
11
11
11
24
26
100

299