새 학기를 맞아서 학생들의 반이 새롭게 배정되었다. 학생들은 N명이고 총 M개의 반으로 배정되었다. 학생들은 순서대로 각 반 교실에 들어간다. 새로운 학생이 들어오면 그 교실이 소란스러워지는데, 그 정도는 그 교실에 들어간 학생의 수와 같다. 학생들이 내는 소음이 선생님들에게는 매우 불편하기 때문에, 선생님은 학생이 들어올 때마다 지도를 통해 조용히 시킨다. 한편, 선생님은 학생들의 소음을 줄이기 위해 한 반의 학생들을 모두 집으로 보낼 수 있다. 학생들을 집으로 보내는 일은 새 학생이 들어온 후에 진행하며, 한 번에 최대 한 반의 학생들만 집으로 보낼 수 있다. 이 작업은 매우 번거롭기 때문에 최대 K번 진행한다.

소음의 크기는 학생들이 들어온 직후 그 교실에서만 측정한다. 이런 방법으로 소음의 크기를 총 N번 측정할 때, 그 합이 최소가 되게 학생들을 집으로 보내는 방법을 구하여라.

입력

• 첫 번째 줄에는 학생의 수 N, 반의 수 M, 학생들을 집으로 보내는 최대 횟수 K가 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 100, 1 ≤ K ≤ 500)
• 두 번째 줄부터 N개의 줄에는 각 학생이 소속한 반의 번호를 나타내는 1 이상 M 이하의 자연수가 주어진다.

 
전체 데이터의 40%는 M = 1이다.
전체 데이터의 60%는 N ≤ 1,000이다.
전체 데이터의 80%는 N ≤ 50,000이다.

출력

입출력 예

입력 예 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

입력 예 1 설명
2번째 학생과 4번째 학생이 들어온 후 1반의 학생들을 집으로 보내면 소음의 크기는 1, 2, 1, 2, 1이다.

입력 예 2 설명
4번째 학생과 8번째 학생이 들어온 후 1반의 학생들을 집으로 보내고 6번째 학생이 들어온 후 2반의 학생들을 집으로 보내면 소음의 크기는 1, 1, 2, 2, 1, 3, 2, 1, 1, 2, 2이다.

출처:coci_2013_2014
번역:functionx