문제
세계 볼링 선수권 대회에 참여하고자 하는 정올국에서는 볼링선수들의 훈련 계획을 세웠다. N명의 선수들의 실력을 수치화 하여 실력이 낮은 사람 K명을 첫 팀으로 다음으로 실력이 낮은 사람 K명을 두 번째 팀으로 등등... N / K팀으로 나누어 훈련시킬 계획이다.
훈련 첫날 전국의 N명의 선수들이 훈련장으로 모여 선수등록을 하려고 줄을 섰다. 선수 등록 담당 형돈이는 선수들이 실력이 낮은 팀부터 높은 팀 순으로 차례로 등록하기를 바란다. 이를 위하여 형돈이는 어떤 위치의 선수 한명을 뽑아 임의의 위치에 재배치하는데 이 때 1분이 소요된다고 한다. 또한 이러한 재배치를 원하는 만큼 할 수 있다고 한다.
전체 선수의 수와 한 팀에 속해야 하는 선수의 수 그리고 각 선수의 실력이 주어질 때 형돈이를 도와 선수들을 줄 세우는데 필요한 시간을 최소화 해보자.
입력
첫 행에 등록 선수의 인원수를 나타내는 N ( 1 ≤ N ≤ 5000)과 각 팀의 구성 인원수 K( N의 약수)가 공백으로 구분되어 입력된다.
다음 행에 N명의 선수들에 대한 실력 Vi ( 1 ≤ Vi ≤ 109) 가 공백으로 구분하여 입력된다. 선수들의 실력은 모두 다르다.
출력
선수들이 실력이 낮은 팀부터 높은 팀 순으로 차례로 재배치하여 줄 세우는데 필요한 최소 시간을 출력한다.
예제1
입력
4 1
9 12 5 13
출력
1
예제2
입력
6 2
16 2 1 7 5 10
출력
1
예제3
입력
6 3
7 9 8 3 6 5
출력
3
출처
COCI 2014/2015 contest2 3