\gdef\thisproblemauthor{Антон Майдель}
\gdef\thisproblemdeveloper{Антон Майдель}
\begin{problem}{Шашки}
{checkers.in}{checkers.out}
{2 секунды (\textsl{3 секунды для Java})}{256 мебибайт}{}

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

С каждым движком Вася последовательно проводит серию партий:
сначала он играет с первым движком, потом со вторым, и так далее.
После серии с последним движком Вася снова играет с первым движком.
Сколько партий будет сыграно в конкретной серии, выбирает Вася,
но серия обязательно должна состоять из одной или из двух партий.

\textit{Цветовой историей} игрока назовём следующую последовательность
цветов: каким цветом играл этот игрок в предыдущей партии,
в пред-предыдущей, и так далее.
Выбор цвета в конкретной партии определяется по следующему алгоритму.
Рассмотрим истории цветов движка и Васи и сравним их как последовательности:
пока предыдущие цвета совпадают, переходим к цветам на одну партию назад.
Если нашлось различие, найденные цвета <<переворачиваются>>.
Если же сыгранных партий недостаточно для того, чтобы определить цвет
по этому алгоритму, Вася будет играть белым цветом.

Например, пусть Вася играл в предыдущей партии чёрными,
а в предпредыдущей "--- белыми.
Далее, пусть движок играл чёрными в двух предыдущих партиях.
Тогда мы сначала сравним чёрный цвет с чёрным (предыдущие партии), а потом
Васин белый с чёрным цветом движка (пред-предыдущие партии) и остановимся
на этом различии.
Эти цвета <<переворачиваются>>: значит, Вася будет играть чёрными,
а движок "--- белыми.

Помогите Васе максимизировать количество партий, сыгранных белым цветом.

\InputFile

Первая строка ввода содержит два положительных целых числа $N$ и $K$,
не превосходящих $20$.
В следующих $N$ строках перечислены цвета,
которыми играли движки до встреч с Васей.
Цвета перечислены в исторической последовательности;
в частности, последним указан цвет, которым движок сыграл предыдущую партию.
Длина каждой такой строки не меньше одного и не больше $100$ символов.
Каждая строка состоит только из символов <<\texttt{W}>> и <<\texttt{B}>>.

\OutputFile

Выведите cтроку, содержащую единственное целое число "--- максимальное
число партий, в которых Вася будет играть белым цветом.

\Examples

\begin{example}
\exmp{%
2 2
W
W
}{%
2
}%
\exmp{%
2 5
W
B
}{%
3
}%
\end{example}

\end{problem}
