Dorm Party

Time limit1sMemory limit256 MB

Summary

Choose up to K building resets over N daily move-ins to minimize the sum of current occupancy counts at each arrival.

Level: Medium6 of 10
Topics: Dynamic programming, Greedy, Math
Solved: No attempts yet

Problem

A new student dorm has opened. It has $M$ buildings, numbered from 1 to $M$ . The dorm starts empty, and over the next $N$ days exactly one student moves in each day.

Every time a student moves into a building, a party is held in that building. The noise of the party equals the number of students inside that building at that moment. The management dislikes noise, so now and then it empties one whole building by moving every resident of that building to a different dorm. The management can empty a building after the end of any day, but it decided that emptying more than $K$ times does not pay off. Emptying one building counts as one time.

You are given which building a student moves into on each day. Find the smallest possible sum of the noise of all $N$ parties when buildings are emptied at most $K$ times.

Input

The first line contains $N$ ( $1 \le N \le 10^6$ ), $M$ ( $1 \le M \le 100$ ) and $K$ ( $1 \le K \le 500$ ).

The $i$ -th of the next $N$ lines contains the number of the building a student moves into on day $i$ . This number is between 1 and $M$ .

Output

Print the smallest possible total noise on one line.

Hint

In the first example the building is emptied after day 1 and after day 3, so the noise values are 1, 1, 2, 1, 2. With no emptying at all they would be 1, 2, 3, 4, 5.

In the second example one option is to empty building 1 after day 4 and after day 8, and building 2 after day 6. The noise values are then 1, 1, 2, 2, 1, 3, 2, 1, 1, 2, 2.

Examples2

Example 1
Input
```
5 1 2
1
1
1
1
1
```
Expected output
```
7
```
Example 2
Input
```
11 2 3
1
2
1
2
1
2
1
2
1
2
1
```
Expected output
```
18
```