— А Принц — в какие игры он играет? — Принцесса внимательно смотрела на Дракона.

— Принц... У него всегда столько разных дел, что на игры, наверное, просто времени не остаётся, — Дракон подумал немного и добавил, — А может быть, он не хочет играть, и поэтому всегда находит много разных дел.

Принц старается работать как можно более эффективно. Так, некоторое время назад Принц выяснил, что если он занимается одним и тем же делом дольше, чем одну единицу времени, эффективность его работы заметно снижается. Поэтому теперь он старается чередовать дела.

А еще Принц ведет учет проделанной работы. Позанимавшись некоторым делом в течение одной единицы времени, он закрашивает на бумажной полоске очередную клетку маркером. Дракон как-то заинтересовался, что означают все эти разноцветные квадратики, и Принц пояснил, что для каждого дела предназначен маркер своего цвета. Правда, количество цветов маркеров ограничено, и Принц может использовать маркер одного и того же цвета для разных дел. Но в этом случае каждое из этих дел завершается до того, как Принц начинает следующее.

Принц хвалился своей методикой, упомянув, помимо прочего, что использует еще параметр забывания — некоторое целое число k, максимально допустимое расстояние между клетками одного цвета, если они относятся к одному делу. Конечно, это не значит, что если между клетками одного цвета расстояние не больше k, то они совершенно точно относятся к одному делу. Но если между клетками одного цвета расстояние больше k, они совершенно точно относятся к разным делам.

Дракона заинтересовало минимальное количество разных дел, которые сделал за последнее время Принц. Ваша задача — определить это по заданной раскраске полоски и величине k. Ради простоты обозначений вместо цветов использованы числа.