폐회식

올해의 IOI 폐회식에 여러 서로 다른 단체가 맨 앞줄에 앉도록 초대되었다(국제 정보 올림피아드). 각 사람에게는 좌석이 배정되어 있다. 하지만 IOI의 주최 측은 단체들이 함께 앉기를 선호한다는 사실을 알지 못해 좌석을 다소 무작위로 배정했다. 따라서 사람들은 직접 문제를 해결하기로 한다. 서로 좌석을 교환하여 같은 단체에 속한 사람끼리 나란히 앉은 쌍의 수를 최대화하려 한다. 좌석 교환이 지나치게 혼란스러워지면 주최 측이 화를 낼 것이므로, 각 사람은 최대 한 번만, 그리고 최대 $K$석 떨어진 사람하고만 좌석을 바꿀 수 있도록 정한다.

같은 단체에 속한 사람끼리 나란히 앉은 쌍의 수를 최대 몇 개까지 만들 수 있는가?

채점

제출한 풀이는 여러 테스트 케이스 그룹으로 구성된 테스트 세트로 평가된다. 한 그룹의 점수를 받으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 점수 | 제약 조건

$1$ |$20$| $K=1$, $N \leq 15$, 그리고 단체는 3개이다(A, B, C).

$2$ |$40$| $K=2$이고 단체는 2개이다(A, B).

$3$ |$40$| $K=2$이고 단체는 4개이다(A, B, C, D).

첫째 줄에는 원래 줄의 배치를 나타내는 길이 $N$의 문자열이 주어진다($1 \leq N \leq 30$). 문자열의 각 문자는 해당 위치에 있는 사람이 어느 단체에 속하는지를 나타내며, A, B, C, D 중 하나이다. 둘째 줄에는 사람들이 이동할 수 있는 최대 거리인 정수 $K$가 주어진다($1 \leq K \leq 2$).

유효한 좌석 교환을 통해 만들 수 있는, 같은 단체에 속한 사람끼리 나란히 앉은 쌍의 최대 개수를 정수로 출력한다.

예제 1에서는 첫 번째 사람과 두 번째 사람의 좌석을 교환하고, 세 번째 사람과 네 번째 사람의 좌석을 교환하여 다음 배치를 만들 수 있다: A B B A A A.

예제 2에서는 두 번째 사람과 세 번째 사람의 좌석을 교환하고, 네 번째 사람과 여섯 번째 사람의 좌석을 교환하여 다음 배치를 만들 수 있다: A A C C B B B A.