题目描述

4399又出了一款好玩的小游戏。4399王水在学习dp，有一天它看到了一道关于dp的题目。
这个题目是这个样子的：一开始有n个数，一段区间的价值为这段区间相同的数的对数。我们想把这n个数切成恰好k段区间。之后这n个数的价值为这k段区间的价值和。我们想让最终这n个数的价值和尽可能少。
例如6个数1,1,2,2,3,3要切成3段，一个好方法是切成[1],[1,2],[2,3,3]，这样只有第三个区间有1的价值。因此这6个数的价值为1。
4399王水想让你做这道题，于是他就把题丢给了你。

输入格式

第一行两个数n,k。
接下来一行n个数ai表示这n个数。

输出格式

一个数表示答案。

输入样例

10 2
1 2 1 2 1 2 1 2 1 2

输出样例

8

数据范围

对于30%的数据n<=10。
对于60%的数据n<=1000。
对于100%的数据1<=n<=100000,1<=k<=min(n,20),1<=ai<=n。
其中有30%的数据满足ai完全相同均匀分布在所有数据中。

时间限制

1000ms

空间限制

128MB

P.S

by 4399王水