시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 26 9 8 33.333%

문제

홍준이의 눈 앞에 N개의 색칠된 구슬이 놓여있다. 구슬의 색은 서로 다를 수 있다. 만약 같은 색의 구슬들이 K개 이상 연속되어 있으면 그 구슬들을 없앨 수 있다. 또한 구슬들을 없애는 작업을 미뤘다가 나중에 할 수도 있다. 운이 좋게도 홍준이에게는 구슬이 많이 있어 구슬들 사이에 원하는 색의 구슬을 끼워 넣을 수 있다. 물론, 맨 앞과 맨 뒤에도 놓을 수 있다.

홍준이를 도와 최소 개수의 구슬을 새로 끼워 넣어 모든 구슬을 없애는 프로그램을 작성하시오.

입력

첫 줄에 N과 K가 주어진다. (1 ≤ N ≤ 100, 2 ≤ K ≤ 5)

그리고 다음 줄에 놓여져 있는 구슬의 색이 차례대로 주어진다. 구슬의 색은 1이상 100이하의 자연수로 표현된다.

출력

놓여져 있는 구슬을 모두 없애기 위해 새로 끼워 넣어야되는 구슬의 최소 개수를 출력한다.

예제 입력

2 5
1 1

예제 출력

3

예제 입력 2

5 3
2 2 3 2 2

예제 출력 2

2

예제 입력 3

10 4
3 3 3 3 2 3 1 1 1 3

예제 출력 3

4

힌트