Description

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.

Input Format

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 Format

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

5 1 2
1
1
1
1
1

7

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

18

Hint

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 Contest #1 T5 ZABAVA.

Translated by ChatGPT 5