P6418 [COCI 2014/2015 #1] ZABAVA

A new apartment complex has opened, and it has $m$ buildings. Now there are $n$ students. Each day, exactly one student moves in. After a student enters a building, a party will be held in that building, and the noise index of the party equals the current number of students in that building. However, you may perform up to $k$ operations. In each operation, you can kick all students in one building out of this new apartment complex. Note that the student enters the building first, and only then can you perform an operation. Now find the minimum possible total sum of the noise indices. You do not have to use all operations.

The first line contains three integers $n,m,k$. The next $n$ lines each contain one integer $p$. Line $i$ means that on day $i$, the $i$-th student moves into building $p$.

Output one line: the minimum possible total sum of the noise indices.

#### Sample Explanation #### Explanation for Sample Input/Output 1 You can clear building $1$ on day $1$ and day $3$. Then the noise index for each day is $1,1,2,1,2$. If you never clear, the noise index for each day is $1,2,3,4,5$. #### Explanation for Sample Input/Output 2 Clear building $1$ on day $4$ and day $8$, and clear building $2$ on day $6$. Then the noise index for each day is $1,1,2,2,1,3,2,1,1,2,2$. #### Constraints - For $40$ points, it is guaranteed that $m=1$. - For $60$ points, it is guaranteed that $n\le 10^3$. - For $80$ points, it is guaranteed that $n\le 5\times 10^4$. - For $100\%$ of the testdata, it is guaranteed that $1\le n\le 10^6$, $1\le m\le 100$, $1\le k\le 500$, $1\le p\le m$. #### Notes **The total score for this problem is $140$ points.** This problem is translated from [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. Translated by ChatGPT 5