졸업식

올해 IOI(International Olympiad in Informatics) 졸업식에서 몇몇 단체가 첫 줄에 앉도록 초대받았다. 각 사람에게는 자리가 하나씩 배정되었다. IOI 운영진은 단체들이 함께 앉고 싶어 한다는 사실을 미처 알지 못했기 때문에 자리를 다소 뒤섞어 배정했다. 그래서 사람들은 상황을 직접 해결하기로 했다. 서로 자리를 바꿔서 같은 단체에 속한 사람들이 나란히 앉는 쌍의 수를 최대화하려는 것이다. 운영진은 자리 바꾸기가 너무 어지러워지면 화를 내므로, 각 사람은 최대 한 번만 자리를 바꿀 수 있고, 그때도 $K$칸 이내로 떨어진 사람과만 바꿀 수 있다.

같은 단체에 속한 사람들이 나란히 앉는 쌍의 수는 최대 얼마인가?

첫째 줄에 처음 줄의 상태를 나타내는 길이 $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 배열을 얻을 수 있다.