문제
새로운 학생 기숙사가 완공되었다. 기숙사는 M개의 건물로 구성되어 있고 1 ~ M까지 번호가 매겨져 있다. 기숙사는 초기에는 비어있지만 N명의 학생들이 하루에 한 명씩 입주한다. 새로운 학생이 한 건물에 입주할 때마다 그 건물에서는 파티가 열린다. 파티가 열릴 때는 소음이 발생하는데 소음의 크기레벨은 그 건물에 있는 학생 수와 같다.
기숙사 관리인 기찬이는 유난히 소음을 싫어한다. 그래서 새로운 학생이 기숙사에 입사 할 때는 파티의 소음이 적정수준을 유지하도록 때때로 어느 한 건물을 모두 비워놓는다고 한다. 어떤 건물을 비울 때는 완전히 다른 곳으로 현재 건물의 모든 학생들을 이주시킨다고 한다. 기찬이는 원하는 날에 어느 건물이든 비울 수 있다. 그런데 이러한 건물을 비우는 일은 많은 비용을 발생시키므로 많아야 K번만 할 수 있다고 한다.
기숙사 입주 정보가 주어질 때 입사하는 동안 발생하는 소음 레벨의 총합을 최소화하도록 하는 프로그램을 작성하여 관리인 기찬이를 도와주자.
입력
첫 행에 학생 수 N(1 ≤ N ≤ 1,000,000), 기숙사 건물 수 M( 1 ≤ M ≤ 100), 건물을 비울 수 있는 횟수 K (1 ≤ K ≤ 500) 이 공백을 기준으로 입력된다.
이 후 N개의 행에 Si가 입력되는데 i번째 날에 한 학생이 Si번 건물로 입주하는 정보이다.
출력
입사하는 동안 발생하는 소음레벨의 총합을 최소로 할 때 그 총합을 하나의 행에 출력한다.
<입력 예1 에 대한 설명>
총합이 7이 되는 한 예는 첫 번째, 세 번째 입사 후에 건물을 비운다. 이렇게 하면 소음 레벨은 각각 1, 1, 2, 1, 2가 된다.
건물을 비우지 않는 경우 소음 레벨은 각각 1, 2, 3, 4, 5가 된다.
<입력 예2 에 대한 설명>
총합이 18이 되게 하는 한 가지 방법은 1번 건물은 네 번째, 여덟 번째 날에 비우고, 2번 건물은 여섯 번째 날에 비우면 된다. 이렇게 하면 소음 레벨은 각각 1, 1, 2, 2, 1, 3, 2, 1, 1, 2, 2가 된다.
예제1
입력
512
1
1
1
1
1
출력
7
예제2
입력
1123
1
2
1
2
1
2
1
2
1
2
1
출력
18
출처
COCI 2014/2015 contest1 5