题目描述

译自 COCI 2014.10 T5. Zabava

新的学生公寓刚刚成立！它包含 $M$ 栋楼，编号为 $1$ 到 $M$。学生公寓初始是空的，但是马上就会有 $N$ 个学生入住，每天都会入住一个学生。

每当一个学生入住一栋楼，在这栋楼的内部就会举行一场大型聚会。聚会产生的噪音等于这栋楼内入住的学生数。公寓管理员不喜欢噪音，所以他们偶尔会清空某一栋楼以保持聚会产生的噪音在一个合理的水平。他们会把一栋楼所有的住户迁移到完全不一样的学生公寓里。管理员可以在任意天时做这件事，但是他们意识到这么做超过 $K$ 次是不值得的。

请帮助管理员！知道了每一天学生的入住情况，求出在最多清空一栋楼 $K$ 次时，$N$ 场聚会产生噪音之和的最小值。

输入格式

第一行包含三个整数 $N,M,K$，意义如题目描述。

接下来 $N$ 行，第 $i+1$ 行包含一个在 $[1,M]$ 之间的整数，表示第 $i$ 天学生入住的楼栋编号。

输出格式

输出一行一个数，表示最小可能产生的噪声和。

5 1 2
1
1
1
1
1

7

11 2 3
1
2
1
2
1
2
1
2
1
2
1

18

数据范围与提示

有两组数据，保证 $M=1$；

有三组数据，保证 $N\le 10^3$；

有四组数据，保证 $N\le 5\times 10^4$；

对于全部数据，$1\le N\le 10^6,1\le M\le 100,1\le K\le 500$。