시간 제한 메모리 제한 제출 횟수 정답 횟수 (비율) 정답자 수
1.0 초 512 MB 1 1 (100%) 1
문제
새로운 학생 기숙사가 개설되었다. 새 기숙사는 $1$부터 $M$까지 차례대로 넘버링 된 $M$개의 건물로 이루어져 있다. 현재 기숙사는 비어 있지만 곧 $N$명의 학생들이 $1$일 $1$학생 씩 입주할 것이다. 새 학생이 어떤 건물에 입주할 때마다 그 건물에선 큰 파티가 열리게 된다. 어떤 파티의 소음은 그 건물에 있는 학생들의 수와 같다. 기숙사 관리 측에서는 소음을 그다지 좋아하지 않기 때문에 특정 건물을 전부 비우게 된다. 이는 그 건물의 학생들을 완전히 다른 기숙사로 옮기면서 이루어진다. 기숙사 관리 측에선 이걸 언제나 할 수 있지만, 최대 $K$번 하는 것이 가장 합리적임을 깨달았다. 관리 측을 도와, 학생들이 어느 건물로 입주하는 지 알았을 때 N개의 파티의 소음 합을 최소화하는 방안을 찾아줘야 한다. 최대 $K$번의 조치가 이루어질 수 있다.
입력
첫 줄엔 $N (1 \le N \le 1,000,000)$, $M (1 \le M \le 100)$, $K (1 \le K \le 500)$가 주어진다. 다음 $N$개의 줄 중 $i$번째 줄엔 $i$번째 날에 입주하는 학생이 어떤 건물로 입주하는 지 정보가 주어진다 (건물 번호는 $[1:M]$ 구간 안에 있다).
출력
한 줄에 소음의 총합의 최솟값을 출력한다.
힌트
##### 입력 예제 1 ``` 5 1 2 1 1 1 1 1 ``` ##### 출력 예제 1 ``` 7 ``` ##### 입력 예제 2 ``` 11 2 3 1 2 1 2 1 2 1 2 1 2 1 ``` ##### 출력 예제 2 ``` 18 ```