题目描述

徐老师在杭州，虽然杭州风景不错，但是交通每天都很堵很堵，导致徐老师上班天天迟到，终于有一天杭州新开通了一条包含 $m$ 条车道的快速路，用于疏导车流。

现假设接下来的一段时间内，有 $n$ 辆车依次驶入该快速路（每秒驶入一辆），每辆车回选择一条车道进入。每当某条车道新进入一辆车时，这条车道便会产生“拥堵值”，“拥堵值”等于当前这条车道内已有的车辆总数（包含刚进入的这辆）。

不过，交通管理部门有 $k$ 次 "加快放行，清空车道"的操作机会：每次操作可以将某一条车道内的所有车辆清空，即该车道后续再驶入车辆时，重新从 $1$ 开始计算车辆数。需要注意的是，车辆先进车道产生“拥堵值”，之后才允许执行清空操作。

请你合理规划这 $k$ 次操作的使用时机（也可以不用完），使得所有车辆驶入车道后，“拥堵值”之和最小。

输入格式

第一行三个整数 $n,m,k$，分别表示车辆总数、车道数量、可清空操作次数；

接下来的 $n$ 行， 每行一个整数 $p$， 第 $i$ 行表示第 $i$ 辆车驶入了第 $p$ 条车道。

输出格式

一个整数，表示最小的“拥堵值”之和。

样例数据

输入样例1

5 1 2
1
1
1
1
1

输出样例1

7

解释：可以在第一辆和第三辆车驶入后执行清空操作，这样每辆车驶入后的拥堵值分别为：1 1 2 1 2，无法得到比 $7$ 更小的结果。

输入样例2

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

输出样例2

18

数据范围

对于所有的测试数据，$1 \le n \le 2 \times 10^6$，$1 \le m \le 100$， $1 \le k \le 500$，$1 \le p \le m$。

【提示】数据输入的规模可能较大，请选手注意输入读取方式的效率。