시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB131322623.636%

문제

2K개의 글자로 이루어진 단어 N개가 주어진다.

코코스는 글자 하나를 포함하고 있는 정점으로 이루어진 유향 그래프(Directed graph)를 말한다. 이때, 모든 단어는 그래프 상의 경로가 존재해야 하며, 이 경로에 쓰여 있는 글자를 순서대로 적었을 때 단어와 일치해야 한다. 

또한, 경로 상의 모든 정점은 아래와 같은 네 가지 조건을 만족해야 한다.

  • 첫 정점의 in-degree는 0이다.
  • 다음 K-1개 정점의 in-degree는 1이다.
  • 다음 K-1개 정점의 out-degree는 1이다.
  • 마지막 정점의 out-degree는 0이다.

위의 조건은 경로는 첫 K개 글자에서 나누어질 수 있고, 마지막 K개 글자에서 만날 수 있음을 의미한다.

단어 N개가 주어진다. 이때, 정점의 수가 가장 적은 코코스를 구하는 프로그램을 작성하시오.

아래 그림은 예제를 정점의 수가 가장 적은 코코스로 나타낸 것이다.

아래 그래프는 위의 그래프보다 정점의 수가 적지만, 코코스가 아니다.

위의 그래프가 코코스가 아닌 이유는 4번째 글자 D에서 경로가 만나고, 6번째 글자 E에서 경로가 갈라져 문제의 조건을 만족하지 않기 때문이다.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10,000, 1 ≤ K ≤ 100)

다음 N개 줄에는 알파벳 대문자로만 이루어진 단어가 주어진다.

출력

첫째 줄에 정점의 수가 가장 적은 코코스의 정점의 수를 출력한다.

예제 입력 1

2 4
ABCDEFGH
EFGHIJKL

예제 출력 1

16

예제 입력 2

4 3
XXZZXX
XXYYZZ
AABBCZ
ABCZZZ

예제 출력 2

18

예제 입력 3

4 4
ABCDEFGH
ACBDEFGH
ABDCFEHG
EFEFFEGH

예제 출력 3

23
W3sicHJvYmxlbV9pZCI6IjMxNzgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNmNTRcdWNmNTRcdWMyYTQiLCJkZXNjcmlwdGlvbiI6IjxwPjJLXHVhYzFjXHVjNzU4IFx1YWUwMFx1Yzc5MFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHViMmU4XHVjNWI0IE5cdWFjMWNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWNmNTRcdWNmNTRcdWMyYTRcdWIyOTQgXHVhZTAwXHVjNzkwIFx1ZDU1OFx1YjA5OFx1Yjk3YyBcdWQzZWNcdWQ1NjhcdWQ1NThcdWFjZTAgXHVjNzg4XHViMjk0IFx1YzgxNVx1YzgxMFx1YzczY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHVjNzIwXHVkNWE1IFx1YWRmOFx1Yjc5OFx1ZDUwNChEaXJlY3RlZCBncmFwaClcdWI5N2MgXHViOWQwXHVkNTVjXHViMmU0LiBcdWM3NzRcdWI1NGMsIFx1YmFhOFx1YjRlMCBcdWIyZThcdWM1YjRcdWIyOTQgXHVhZGY4XHViNzk4XHVkNTA0IFx1YzBjMVx1Yzc1OCBcdWFjYmRcdWI4NWNcdWFjMDAgXHVjODc0XHVjN2FjXHVkNTc0XHVjNTdjIFx1ZDU1OFx1YmE3MCwgXHVjNzc0IFx1YWNiZFx1Yjg1Y1x1YzVkMCBcdWM0ZjBcdWM1ZWMgXHVjNzg4XHViMjk0IFx1YWUwMFx1Yzc5MFx1Yjk3YyBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjODAxXHVjNWM4XHVjNzQ0IFx1YjU0YyBcdWIyZThcdWM1YjRcdWM2NDAgXHVjNzdjXHVjZTU4XHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+XHViNjEwXHVkNTVjLCBcdWFjYmRcdWI4NWMgXHVjMGMxXHVjNzU4IFx1YmFhOFx1YjRlMCBcdWM4MTVcdWM4MTBcdWM3NDAgXHVjNTQ0XHViNzk4XHVjNjQwIFx1YWMxOVx1Yzc0MCBcdWIxMjQgXHVhYzAwXHVjOWMwIFx1Yzg3MFx1YWM3NFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlx1Y2NhYiBcdWM4MTVcdWM4MTBcdWM3NTggaW4tZGVncmVlXHViMjk0IDBcdWM3NzRcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YjJlNFx1Yzc0YyBLLTFcdWFjMWMgXHVjODE1XHVjODEwXHVjNzU4IGluLWRlZ3JlZVx1YjI5NCAxXHVjNzc0XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWIyZTRcdWM3NGMgSy0xXHVhYzFjIFx1YzgxNVx1YzgxMFx1Yzc1OCBvdXQtZGVncmVlXHViMjk0IDFcdWM3NzRcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YjljOFx1YzljMFx1YjljOSBcdWM4MTVcdWM4MTBcdWM3NTggb3V0LWRlZ3JlZVx1YjI5NCAwXHVjNzc0XHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1YzcwNFx1Yzc1OCBcdWM4NzBcdWFjNzRcdWM3NDAgXHVhY2JkXHViODVjXHViMjk0IFx1Y2NhYiBLXHVhYzFjIFx1YWUwMFx1Yzc5MFx1YzVkMFx1YzExYyBcdWIwOThcdWIyMDRcdWM1YjRcdWM5YzggXHVjMjE4IFx1Yzc4OFx1YWNlMCwgXHViOWM4XHVjOWMwXHViOWM5IEtcdWFjMWMgXHVhZTAwXHVjNzkwXHVjNWQwXHVjMTFjIFx1YjljY1x1YjBhMCBcdWMyMTggXHVjNzg4XHVjNzRjXHVjNzQ0IFx1Yzc1OFx1YmJmOFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMmU4XHVjNWI0IE5cdWFjMWNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzRcdWI1NGMsIFx1YzgxNVx1YzgxMFx1Yzc1OCBcdWMyMThcdWFjMDAgXHVhYzAwXHVjN2E1IFx1YzgwMVx1Yzc0MCBcdWNmNTRcdWNmNTRcdWMyYTRcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuXHJcbjxwPlx1YzU0NFx1Yjc5OCBcdWFkZjhcdWI5YmNcdWM3NDAgXHVjNjA4XHVjODFjXHViOTdjIFx1YzgxNVx1YzgxMFx1Yzc1OCBcdWMyMThcdWFjMDAgXHVhYzAwXHVjN2E1IFx1YzgwMVx1Yzc0MCBcdWNmNTRcdWNmNTRcdWMyYTRcdWI4NWMgXHViMDk4XHVkMGMwXHViMGI4IFx1YWM4M1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC9kNDY5ZWY1ZC1jMTUzLTQ0M2UtYWM4Ny1hZDYwM2QxY2M3YTFcLy1cL3ByZXZpZXdcL1wiIHN0eWxlPVwid2lkdGg6IDQ2MXB4OyBoZWlnaHQ6IDE4MHB4O1wiIFwvPjxcL3A+XHJcblxyXG48cD5cdWM1NDRcdWI3OTggXHVhZGY4XHViNzk4XHVkNTA0XHViMjk0IFx1YzcwNFx1Yzc1OCBcdWFkZjhcdWI3OThcdWQ1MDRcdWJjZjRcdWIyZTQgXHVjODE1XHVjODEwXHVjNzU4IFx1YzIxOFx1YWMwMCBcdWM4MDFcdWM5YzBcdWI5Y2MsIFx1Y2Y1NFx1Y2Y1NFx1YzJhNFx1YWMwMCBcdWM1NDRcdWIyYzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL3VwbG9hZC5hY21pY3BjLm5ldFwvZDAzYmYxNDMtNDM3ZS00MzE3LWJiOTctYTg4M2JkZmU1Y2NiXC8tXC9wcmV2aWV3XC9cIiBzdHlsZT1cIndpZHRoOiA0NjFweDsgaGVpZ2h0OiAxNzlweDtcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVjNzA0XHVjNzU4IFx1YWRmOFx1Yjc5OFx1ZDUwNFx1YWMwMCBcdWNmNTRcdWNmNTRcdWMyYTRcdWFjMDAgXHVjNTQ0XHViMmNjIFx1Yzc3NFx1YzcyMFx1YjI5NCA0XHViYzg4XHVjOWY4IFx1YWUwMFx1Yzc5MCBEXHVjNWQwXHVjMTFjIFx1YWNiZFx1Yjg1Y1x1YWMwMCBcdWI5Y2NcdWIwOThcdWFjZTAsIDZcdWJjODhcdWM5ZjggXHVhZTAwXHVjNzkwIEVcdWM1ZDBcdWMxMWMgXHVhY2JkXHViODVjXHVhYzAwIFx1YWMwOFx1Yjc3Y1x1YzgzOCBcdWJiMzhcdWM4MWNcdWM3NTggXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YzljMCBcdWM1NGFcdWFlMzAgXHViNTRjXHViYjM4XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBOXHVhY2ZjIEtcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IE4gJmxlOyAxMCwwMDAsIDEgJmxlOyBLICZsZTsgMTAwKTxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgTlx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjNTRjXHVkMzBjXHViY2IzIFx1YjMwMFx1YmIzOFx1Yzc5MFx1Yjg1Y1x1YjljYyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHViMmU4XHVjNWI0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzgxNVx1YzgxMFx1Yzc1OCBcdWMyMThcdWFjMDAgXHVhYzAwXHVjN2E1IFx1YzgwMVx1Yzc0MCBcdWNmNTRcdWNmNTRcdWMyYTRcdWM3NTggXHVjODE1XHVjODEwXHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMzE3OCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Imtva29zIiwiZGVzY3JpcHRpb24iOiI8cD5BIHNldCBvZiBOIHdvcmRzIGlzIGdpdmVuIHdpdGggdGhlIGxlbmd0aCBvZiBlYWNoIHdvcmQgYmVpbmcgZXhhY3RseSAySyBjaGFyYWN0ZXJzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5BIGRpcmVjdGVkIGdyYXBoIHdpdGggZWFjaCB2ZXJ0ZXggY29udGFpbmluZyBhIHNpbmdsZSBsZXR0ZXIgaXMgY2FsbGVkIGEgJnF1b3Q7a29rb3MmcXVvdDsgaWYsIGZvciBlYWNoIHdvcmQgaW4gdGhlIHNldCwgdGhlcmUgZXhpc3RzIGEgZGlyZWN0ZWQgcGF0aCBpbiB0aGUgZ3JhcGggc3VjaCB0aGF0IHRoZSBsYWJlbHMgb24gdGhlIHZlcnRpY2VzIGFsb25nIHRoYXQgcGF0aCBmb3JtIHRoZSB3b3JkLiBBZGRpdGlvbmFsbHksIGZvciBhbGwgdmVydGljZXMgb24gdGhhdCBwYXRoIHRoZSBmb2xsb3dpbmcgY29uZGl0aW9ucyBoYXZlIHRvIGJlIHNhdGlzZmllZDombmJzcDs8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT50aGUgaW4tZGVncmVlIG9mIHRoZSBmaXJzdCB2ZXJ0ZXggaXMgMCZuYnNwOzxcL2xpPlxyXG5cdDxsaT50aGUgaW4tZGVncmVlcyBvZiB0aGUgbmV4dCBLLTEgdmVydGljZXMgaXMgMSZuYnNwOzxcL2xpPlxyXG5cdDxsaT50aGUgb3V0LWRlZ3JlZXMgb2YgdGhlIG5leHQgSy0xIHZlcnRpY2VzIGlzIDEmbmJzcDs8XC9saT5cclxuXHQ8bGk+dGhlIG91dC1kZWdyZWUgb2YgdGhlIGxhc3QgdmVydGV4IGlzIDAmbmJzcDs8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5JbiBvdGhlciB3b3JkcywgcGF0aHMgY2FuIGZvcmsgb25seSBvbiB0aGUgZmlyc3QgSyBsZXR0ZXJzLCBhbmQgdGhleSBjYW4gbWVldCBvbmx5IG9uIHRoZSBsYXN0IEsgbGV0dGVycy48XC9wPlxyXG5cclxuPHA+Rm9yIHRoZSBnaXZlbiBzZXQgb2YgdGhlIHdvcmRzLCB3ZSBzYXkgdGhhdCB0aGUgJnF1b3Q7a29rb3MmcXVvdDsgaXMgbWluaW1hbCBpZiB0aGUgdG90YWwgbnVtYmVyIG9mIHZlcnRpY2VzIGlzIGFzIHNtYWxsIGFzIHBvc3NpYmxlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdGhhdCB3aWxsIGZpbmQgdGhlIG51bWJlciBvZiB2ZXJ0aWNlcyBpbiBhIG1pbmltYWwga29rb3MuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkFuIGV4YW1wbGUgb2YgYSBtaW5pbWFsIGtva29zICh0aGUgc2V0IG9mIHRoZSB3b3JkcyBpcyBmcm9tIHRoZSB0aGlyZCBleGFtcGxlKTo8XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC9kNDY5ZWY1ZC1jMTUzLTQ0M2UtYWM4Ny1hZDYwM2QxY2M3YTFcLy1cL3ByZXZpZXdcL1wiIHN0eWxlPVwid2lkdGg6IDQ2MXB4OyBoZWlnaHQ6IDE4MHB4O1wiIFwvPjxcL3A+XHJcblxyXG48cD5JdCBtYXkgc2VlbSB0aGF0IHdlIGNhbiBjb21wYWN0IHRoZSBncmFwaCBsaWtlIHRoaXM6PFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL3VwbG9hZC5hY21pY3BjLm5ldFwvZDAzYmYxNDMtNDM3ZS00MzE3LWJiOTctYTg4M2JkZmU1Y2NiXC8tXC9wcmV2aWV3XC9cIiBzdHlsZT1cIndpZHRoOiA0NjFweDsgaGVpZ2h0OiAxNzlweDtcIiBcLz48XC9wPlxyXG5cclxuPHA+SG93ZXZlciwgdGhpcyBncmFwaCBpcyBub3QgYSBrb2tvcyBiZWNhdXNlIHBhdGhzIG1lZXQgb24gdGhlIDR0aCBsZXR0ZXIgKEQpLCBhbmQgdGhleSBmb3JrIG9uIHRoZSA2dGggbGV0dGVyIChFKS4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHR3byBpbnRlZ2VycyBOIGFuZCBLLCAxICZsZTsgTiAmbGU7IDEwIDAwMCwgMSAmbGU7IEsgJmxlOyAxMDAuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkVhY2ggb2YgdGhlIGZvbGxvd2luZyBOIGxpbmVzIGNvbnRhaW5zIG9uZSB3b3JkIGZyb20gdGhlIHNldC4gQWxsIGxldHRlcnMgd2lsbCBiZSB1cHBlcmNhc2UgbGV0dGVycyBvZiB0aGUgRW5nbGlzaCBhbHBoYWJldCAoJiMzOTtBJiMzOTstJiMzOTtaJiMzOTspLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBmaXJzdCBhbmQgb25seSBsaW5lIG9mIG91dHB1dCBzaG91bGQgY29udGFpbiB0aGUgbnVtYmVyIG9mIHZlcnRpY2VzIGluIGEgbWluaW1hbCBrb2tvcy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d