Clearing the Beads

Time limit1sMemory limit128 MB

Summary

Find the minimum number of beads to insert between colored beads so every bead can eventually be cleared by removing runs of length at least K.

Level: Medium7 of 10
Topics: Dynamic programming, Stack, Recursion
Solved: No attempts yet

Problem

There are N colored beads placed in a row in front of Hongjun. Beads may share colors or all differ. Whenever K or more beads of the same color are next to each other, that whole run of beads can be cleared at once. Clearing does not have to be done right away; it may be postponed until later.

Hongjun has plenty of spare beads, so he may insert a bead of any color he likes into any gap between the existing beads, including before the first bead and after the last bead.

Write a program that finds the minimum number of beads he must insert so that, eventually, every bead can be cleared.

Input

The first line contains N and K. (1 ≤ N ≤ 100, 2 ≤ K ≤ 5)

The second line contains the colors of the beads in order from left to right. Each color is a natural number between 1 and 100 inclusive.

Output

Print the minimum number of beads that must be inserted in order to clear all of the beads.

Examples3

Example 1
Input
```
2 5
1 1
```
Expected output
```
3
```
Example 2
Input
```
5 3
2 2 3 2 2
```
Expected output
```
2
```
Example 3
Input
```
10 4
3 3 3 3 2 3 1 1 1 3
```
Expected output
```
4
```