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
