题目描述

一座新的公寓开放了，这座公寓有 $m$ 栋楼。

现在会有 $n$ 个学生，每一天都会进来一个人。

一栋楼进来一个人后，会进行一场派对，派对会有与当前人数相等的吵闹指数。

但是，现在可以进行 $k$ 次操作，每一次操作可以将一栋楼里的全部学生踢出这座新公寓。

请注意，学生先进楼，然后才能进行操作。

现在求出最小吵闹指数的相加之和。

你不必使用完全部的操作。

输入格式

第一行为三个整数 $n,m,k$。

接下来 $n$ 行，一行一个整数 $p$，第 $i$ 行表示在第 $i$ 天，第 $i$ 个同学搬进了第 $p$ 栋楼。

输出格式

仅一行，表示最小吵闹指数的相加之和。

5 1 2
1
1
1
1
1

7

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

18

提示

样例说明

样例输入输出 1 说明

可以在第一天和第三天清空第一栋楼，这样每一天的吵闹指数为 $1,1,2,1,2$，如果不清空每一天的吵闹指数为 $1,2,3,4,5$。

样例输入输出 2 说明

在第四天和第八天清空第一栋楼，在第六天清空第二栋楼，这样每一天的吵闹指数为 $1,1,2,2,1,3,2,1,1,2,2$。

数据范围及限制

• 对于 $40$ 分的数据，保证 $m=1$。
• 对于 $60$ 分的数据，保证 $n\le 10^3$。
• 对于 $80$ 分的数据，保证 $n\le 5\times 10^4$。
• 对于 $100\%$ 的数据，保证 $1\le n\le 10^6$，$1\le m\le 100$，$1\le k\le 500$，$1\le p\le m$。

说明

本题总分 $140$ 分。

本题译自 Croatian Open Competition in Informatics 2014/2015 Contest #1 T5 ZABAVA。