도난당한 문자열

당신과 공범 Acsel은 적 Waxel에게서 길이가 $n$인 문자열을 훔쳤다. 이제 각자가 모든 문자에 대해 정확히 같은 개수를 받도록 문자열을 나누려고 한다. 하지만 문자열을 자르는 데는 비용이 많이 들므로, 전리품을 똑같이 나누는 데 필요한 최소 절단 횟수를 구해야 한다.

예를 들어 문자열이 "$\textit{acabbc}$"였다면, 문자열을 "$\textit{a}+\textit{cab}+\textit{bc}$"로 나눌 수 있다. 그러면 당신은 첫 번째 조각과 마지막 조각을 가지고 Acsel은 가운데 조각을 가질 수 있다. 여기서는 두 번 잘라야 하며, 이는 이 경우의 최소 절단 횟수이기도 하다.

점수

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

그룹 | 점수 | 제한

$1$ |$10$| $4 \le n \le 10^5$ , $k = 2$

$2$ |$20$| $4 \le n \le 10^5$ , $k = 3$

$3$ |$10$| $4 \le n \le 20$ , $2 \leq k \leq 10$

$4$ |$15$| $4 \le n \le 40$ , $2 \leq k \leq 6$

$5$ |$45$| $4 \le n \le 40$ , $2 \leq k \leq 12$

첫 번째이자 유일한 줄에는 길이가 $n$이고 문자 'a', 'b', ... , 'a' $+(k-1)$로 이루어진 문자열이 주어진다. $n$와 $k$의 제한은 아래를 참고한다.

필요한 최소 절단 횟수를 나타내는 정수 하나를 출력한다. 전리품을 정확히 똑같이 나눌 수 없다면 ``$-1$''을 출력한다.