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
Peter has found a litter of $$$N$$$ kittens lying around in an alley somewhere and wants to give them up for adoption. However, kittens are trouble, they knock over your ornaments, dirty your house, etc. Luckily, Peter has found a way to measure how much trouble a group of kittens will cause.
Peter first identifies each kitten with two attributes, a naughtiness level $$$A_i$$$ and a cuteness level $$$B_i$$$. If he sends a particular group of cats to one owner, the trouble they will cause is given by the formula $$$\max(A_i) \cdot \max(B_i)$$$ over the group of kittens.
Peter wants to minimize the total trouble caused by these kittens by grouping them optimally and sending them to their new owners in those groups. Help Peter find out what this minimum total trouble is.
The first line of input contains one integer, $$$N$$$ ($$$1 \leq N \leq 300000$$$).
The next $$$N$$$ lines of input contains two integers each, $$$A_i$$$ and $$$B_i$$$ ($$$1 \leq A_i,B_i \leq 1000000$$$).
4 100 1 15 15 20 5 1 100
500