Pekgälsvalsen

Doris는 가족에게 보낼 긴 이메일을 작성하고 있다. 글은 서로 다른 $K$개의 문자로 이루어져 있으며, 길이는 $N$자이다. Doris는 기억력이 그다지 좋지 않아 키보드에서 문자들의 위치를 기억하지 못한다. 대신 글을 쓸 때 이른바 pekgälsvalsen의 변형된 방식을 사용한다.

Doris는 글을 이루는 서로 다른 각 문자마다 한 번씩, 총 $K$번에 걸쳐 글을 작성한다. 처음에 Doris는 한쪽 아가미로 문자 하나의 모든 출현 위치에 그 문자를 적는다. 그런 다음 글의 처음으로 돌아가 새로운 문자를 하나 고른다. 이어서 다른 쪽 아가미로 오른쪽 화살표 키를 사용하면서 이 문자의 모든 출현 위치에 문자를 입력한다. 그 후 다시 글의 처음으로 돌아가 이번에는 세 번째 문자를 적으며, 이와 같은 과정을 계속한다. 글 전체를 작성할 때까지 이를 반복한다. 이렇게 하면 한 번에 문자 하나의 키가 어디에 있는지만 기억하면 된다.

문자를 어떤 순서로 입력하느냐에 따라 걸리는 시간이 달라질 수 있다. 글 aabbac을 입력해야 할 때 a, b, c 순서로 입력하면 오른쪽 화살표 키를 7번 눌러야 한다. 먼저 오른쪽 화살표 키를 사용하지 않고 aaa을 입력한다. 그런 다음 글의 처음으로 돌아가 오른쪽 화살표 키를 두 번 사용하고 bb을 입력한다. 마지막으로 처음으로 돌아가 오른쪽으로 다섯 번 이동한 뒤 c을 입력한다.

대신 b, a, c 순서를 선택했다면 먼저 bb을 입력했을 것이다. 그런 다음 오른쪽 화살표 키를 두 번 눌러 aabba을 입력하고, 마지막으로 추가로 다섯 번 눌러 aabbac을 입력했을 것이다.

c, b, a 순서에서는 오른쪽 화살표 키를 두 번만 누르면 되며, 이것이 최적이다.

채점

제출한 풀이는 여러 테스트 케이스 그룹으로 나누어 채점된다. 한 그룹에서 점수를 얻으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 점수 | 제한

1      |  8  |  $K = 2$, $N \le 100$

2      |  10  |  $K \le 7$, $N \le 100$

3      |  28  |  $K \le 10$, $N \le 1000$

4      |  19  |  $K \le 10$, $N \le 10^6$

5      |  35  |  $K \le 18$, $N \le 10^6$

첫째 줄에 양의 정수 $N$와 $K$가 주어진다. 다음 줄에는 알파벳의 처음 $K$개 소문자(a, b, c, ...) 중에서 고른 문자로 이루어진 길이 $N$의 문자열이 주어진다. 또한 이 문자열에 서로 다른 문자가 정확히 $K$개 포함되어 있음이 보장된다.

Doris가 글을 작성하기 위해 오른쪽 화살표 키를 눌러야 하는 횟수를 나타내는 하나의 수를 출력한다.