SP33372 LARMY - Lannister Army

“Lannister 有债必还。”现在你有机会得到 Jaime Lannister 的报酬了。 在 Jamie 的军队里共有 $N$ 名战士站成一行。 现在 Jamie 想向他的战士们传达一条信息。但是如果战士们全部站在一行中，消息传递是很困难的。 所以 Jaime 想把战士们分成 $K$ 行。每行至少要有一个战士。 设第 $i$ 行第 $j$ 个战士的身高为 $h_{i,j}$。定义第 $i$ 行第 $j$ 个战士的**不快乐度**为在第 $i$ 行的编号小于 $j$ 的战士中，身高高于他的战士的数量。形式化地说，就是 $\sum_{k=1}^{j-1} [h_{i,k}\gt h_{i,j}]$。特别地，每行的第一个战士的不快乐度为 $0$。 战士们开心了，才能打好仗。Jaime 想让你求出分成 $K$ 行后的战士们不快乐度之和最小是多少。 注意：**不允许交换两名战士的顺序。**

输入的第一行包含两个正整数 $N$，$K$，含义见题面。 第二行输入包含 $N$ 个正整数，其中第 $i$ 个数表示第 $i$ 个战士的身高 $h_i$。

输出一行一个整数，即不快乐度之和的最小值。 ### 样例 1 ``` 8 3 20 50 30 60 40 100 5 1 ``` ``` 2 ```

样例中，一个最优解为 ``` 20,50,30,60; 40,100; 5,1; ``` $1\le K\le N\le 5000$，$1\le h_i\le 10^5$。 $\text{Statement fixed by @Starrykiller.}$