P6418 [COCI 2014/2015 #1] ZABAVA

一座新的公寓开放了，这座公寓有 $m$ 栋楼。 现在会有 $n$ 个学生，每一天都会进来一个人。 一栋楼进来一个人后，会进行一场派对，派对会有与当前人数相等的吵闹指数。 但是，现在可以进行 $k$ 次操作，每一次操作可以将一栋楼里的全部学生踢出这座新公寓。 请注意，学生先进楼，然后才能进行操作。 现在求出最小吵闹指数的相加之和。 你不必使用完全部的操作。

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

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

#### 样例说明 #### 样例输入输出 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](https://hsin.hr/coci/archive/2014_2015) [Contest #1](https://hsin.hr/coci/archive/2014_2015/contest1_tasks.pdf) T5 ZABAVA。