햄스터

Byteasar는 햄스터를 기른다. 각 햄스터는 영어 소문자로 이루어진, 서로 다른 고유한 이름을 가진다. 그는 우리 아래에 이름을 보여 줄 전광판을 설치하려고 한다. 전광판은 한 줄로 늘어선 칸들로 이루어지며, 각 칸은 서로 독립적으로 켜지거나 꺼질 수 있다. 어느 순간에도 전광판은 정확히 하나의 이름만 보여 준다. 이름을 이루는 켜진 칸들은 서로 이웃해야 하며, 전광판에서 연속한 구간을 이루어야 한다.

Byteasar는 햄스터 이름들을 전광판의 서로 다른 위치에 합쳐서 최소 $m$번 보여 줄 수 있을 만큼 전광판을 충분히 길게 만들고 싶다. 같은 이름을 여러 위치에 보여 주어도 되고, 이름의 등장은 서로 겹쳐도 되며, 모든 햄스터의 이름을 보여 줄 수 있어야 하는 것은 아니다. 어떤 햄스터의 이름도 다른 햄스터 이름의 연속한 부분 문자열로 등장하지 않음이 보장된다.

바꾸어 말하면, 햄스터 이름들이 (중복을 포함하여) 전체에서 최소 $m$번 등장하는, 영어 소문자로 이루어진 문자열의 최소 길이를 구하여라. 문자열 $s$가 문자열 $t$에 등장한다는 것은 $s$가 $t$의 연속한 부분 문자열이라는 뜻이다.

첫 줄에 두 정수 $n$과 $m$이 공백 하나로 구분되어 주어진다 ($1 \le n \le 200$, $1 \le m \le 10^9$). $n$은 햄스터의 수, $m$은 필요한 이름 등장 횟수의 최솟값이다. 이어지는 $n$개의 줄에는 비어 있지 않은 영어 소문자 문자열이 한 줄에 하나씩 주어지며, 각각 햄스터의 이름이다. 모든 이름의 길이의 합은 $100{,}000$을 넘지 않는다.

전광판이 가져야 하는 최소 칸 수를 정수 하나로 출력한다.

예시에서 가장 짧은 전광판 중 하나는 길이가 $23$인 szymonikatomekszymonika이다. 여기에는 이름이 모두 $5$번 등장한다. szymon과 monika가 각각 두 번, tomek이 한 번 등장하고, bernard는 전혀 등장하지 않는다.