사탕 크로스

이 문제는 인기 있는 사탕 게임을 크게 단순화한 버전이다. 이 버전을 사탕 크로스라고 부르자. 게임판은 $R$개의 칸으로 이루어진 하나의 세로 기둥이다. 각 칸에는 A, B, C 중 한 종류의 사탕이 들어 있다. 최대 $N$번까지 움직일 수 있다. 한 번의 움직임에서는 인접한 두 사탕의 자리를 서로 바꿔서, 같은 사탕이 세 개 이상 이어진 줄을 만든다. 그런 움직임이 전혀 없으면 게임이 끝난다.

움직임을 하면 줄에 속한 사탕이 모두 사라진다. 여러 줄이 동시에 생기면 모두 함께 사라진다. 그다음 빈 칸은 위에 있던 사탕이 내려와 채운다. 기둥은 항상 새 사탕으로 가득 채워진다. 어떤 새 사탕이 내려올지 정하기 위해, 처음 기둥을 위쪽으로 무한히 높게 복사한 것을 떠올리면 된다.

빈 칸을 다 채우면 새로운 상황이 생길 수 있고, 이 과정은 자동으로 반복된다. 줄을 이루는 사탕이 사라지고 빈 칸이 다시 채워진다. 판에 줄이 남아 있지 않을 때까지 계속된다. 그 뒤에 다음 움직임을 한다.

점수 계산은 간단하다. 세 개 이상의 사탕으로 이루어진 줄이 생길 때마다, 그것이 내가 한 움직임 때문이든 떨어진 사탕 때문이든, 줄의 길이를 $L$이라 할 때 $(2L-5)$점을 얻는다. 길이가 3인 줄은 1점, 길이가 4인 줄은 3점이다.

처음 기둥과 최대 움직임 횟수가 주어졌을 때, 얻을 수 있는 최대 점수를 계산하는 프로그램을 작성하라.

첫 줄에 최대 움직임 횟수인 정수 $N$이 주어진다 ($1 \le N \le 5$). 둘째 줄에는 A, B, C로만 이루어진 길이 $R$의 문자열이 주어진다 ($3 \le R \le 20$). 이것이 처음 기둥이며, 아래에서 위 순서로 적혀 있다. 처음 기둥에는 같은 문자가 세 개 연속으로 나오지 않는다. 입력은 사탕이 끝없이 떨어지는 무한 반복이 생기지 않도록 고른 것이다.

얻을 수 있는 최대 점수를 나타내는 정수 하나를 출력한다.

$2 \le N \le 5$