나중에 보기

YouTube 동영상을 탐색할 때, 흔히 나중에 볼 동영상에 추가라는 아주 편리한 기능을 사용한다. 어느 날 마침내 `Later'가 찾아왔다고 판단하게 되었는데, 목록에는 동영상이 아주 많이 쌓여 있다.

서로 다른 유형의 동영상으로 이루어진 목록이 있다. 예를 들어, 일부는 볼더링 동영상일 수도 있고, 일부는 고양이 동영상일 수도 있으며, 그 밖의 유형도 있을 수 있다. 서로 다른 유형의 동영상을 보기 전에 같은 유형의 모든 동영상을 보고 싶지만, 동영상 유형을 보는 순서는 원하는 대로 정할 수 있다. 예를 들어, 고양이 동영상을 보기 전에 모든 볼더링 동영상을 보고 싶을 수 있다.

시청을 시작하려면 동영상을 클릭하여 재생해야 한다. 목록에 있는 어떤 동영상이든 클릭하여 해당 동영상의 시청을 시작할 수 있다. 동영상의 재생이 끝날 때마다 목록에서 자동으로 삭제된다. 동영상의 재생이 끝나도 남아 있는 동영상의 순서는 바뀌지 않는다. 또한 목록에서 바로 다음 동영상의 유형이 방금 시청한 동영상과 같다면 그 동영상이 자동으로 재생된다. 유형이 다르거나 방금 시청한 동영상 뒤에 동영상이 없다면, 더 많은 동영상을 시청하기 위해 목록에 있는 다른 동영상을 클릭해야 한다(이미 모든 동영상을 시청한 경우는 제외한다).

Watch Later 목록에 대한 설명이 주어질 때, 위에서 설명한 제약을 지키며 모든 동영상을 시청하는 데 필요한 최소 클릭 횟수는 얼마인가?

입력의 첫째 줄에는 두 정수 $n$ ($1 \leq n \leq 400$), 즉 Watch Later 목록에 있는 동영상의 개수와, $k$ ($1 \leq k \leq 20$), 즉 목록에 있는 서로 다른 동영상 유형의 개수가 주어진다.

입력의 둘째 줄에는 Watch Later 목록을 설명하는 길이 $n$의 문자열이 주어진다. 문자열의 $i^\textrm{th}$ 문자는 $i^\textrm{th}$ 동영상의 유형을 나타내는 영문 소문자이다. 두 동영상은 같은 문자로 나타낸 경우에만 같은 유형이다.

현재 Watch Later 목록에 있는 모든 동영상을 시청하는 데 필요한 최소 클릭 횟수를 나타내는 정수 하나를 한 줄에 출력한다.