기숙사 파티

시간 제한1초메모리 제한256 MB

요약

N일간 건물별 입주 순서가 주어질 때 건물 전체를 최대 K번 비워 각 입주 시점의 거주자 수 합을 최소화합니다.

난이도: 보통10점 중 6점
유형: 동적 계획법, 그리디, 수학
정답자: 아직 제출이 없습니다

문제

새 학생 기숙사가 문을 열었다. 기숙사는 1번부터 $M$ 번까지 번호가 붙은 건물 $M$ 개로 이루어져 있다. 처음에는 아무도 살지 않지만, 앞으로 $N$ 일 동안 하루에 정확히 한 명씩 학생 $N$ 명이 들어온다.

학생이 어떤 건물로 들어올 때마다 그 건물에서 파티가 열린다. 파티의 소음은 그 시점에 그 건물 안에 있는 학생 수와 같다. 관리실은 소음을 싫어해서 가끔 건물 하나를 통째로 비운다. 그 건물에 사는 학생을 모두 다른 기숙사로 옮기는 방식이다. 관리실은 어느 날이든 그날이 끝난 뒤에 건물을 비울 수 있지만, $K$ 번보다 많이 비우는 것은 이득이 없다고 판단했다. 건물 하나를 비우는 것이 한 번이다.

며칠째에 어느 건물로 학생이 들어오는지 주어진다. 건물을 최대 $K$ 번 비워서 만들 수 있는 파티 $N$ 개의 소음 합의 최솟값을 구하라.

입력

첫째 줄에 $N$ ( $1 \le N \le 10^6$ ), $M$ ( $1 \le M \le 100$ ), $K$ ( $1 \le K \le 500$ )이 주어진다.

이어지는 $N$ 개의 줄 중 $i$ 번째 줄에는 $i$ 일째에 학생이 들어오는 건물의 번호가 주어진다. 이 번호는 1 이상 $M$ 이하이다.

출력

파티 $N$ 개의 소음 합의 최솟값을 한 줄에 출력한다.

힌트

첫 번째 예제에서는 1일과 3일이 끝난 뒤에 건물을 비운다. 소음은 차례대로 1, 1, 2, 1, 2이다. 한 번도 비우지 않으면 소음은 1, 2, 3, 4, 5가 된다.

두 번째 예제에서는 1번 건물을 4일과 8일이 끝난 뒤에, 2번 건물을 6일이 끝난 뒤에 비우는 방법이 있다. 이때 소음은 차례대로 1, 1, 2, 2, 1, 3, 2, 1, 1, 2, 2이다.

예제2

예제 1
입력
```
5 1 2
1
1
1
1
1
```
예상 출력
```
7
```
예제 2
입력
```
11 2 3
1
2
1
2
1
2
1
2
1
2
1
```
예상 출력
```
18
```