시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 116 31 25 26.316%

문제

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

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

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

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

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

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

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

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

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

입력

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

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

출력

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

예제 입력 1

4 4
ABCDEFGH
ACBDEFGH
ABDCFEHG
EFEFFEGH

예제 출력 1

23
W3sicHJvYmxlbV9pZCI6IjMxNzgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNmNTRcdWNmNTRcdWMyYTQiLCJkZXNjcmlwdGlvbiI6IjxwPjJLXHVhYzFjXHVjNzU4IFx1YWUwMFx1Yzc5MFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHViMmU4XHVjNWI0IE5cdWFjMWNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWNmNTRcdWNmNTRcdWMyYTRcdWIyOTQgXHVhZTAwXHVjNzkwIFx1ZDU1OFx1YjA5OFx1Yjk3YyBcdWQzZWNcdWQ1NjhcdWQ1NThcdWFjZTAgXHVjNzg4XHViMjk0IFx1YzgxNVx1YzgxMFx1YzczY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHVjNzIwXHVkNWE1IFx1YWRmOFx1Yjc5OFx1ZDUwNChEaXJlY3RlZCBncmFwaClcdWI5N2MgXHViOWQwXHVkNTVjXHViMmU0LiBcdWM3NzRcdWI1NGMsIFx1YmFhOFx1YjRlMCBcdWIyZThcdWM1YjRcdWIyOTQgXHVhZGY4XHViNzk4XHVkNTA0IFx1YzBjMVx1Yzc1OCBcdWFjYmRcdWI4NWNcdWFjMDAgXHVjODc0XHVjN2FjXHVkNTc0XHVjNTdjIFx1ZDU1OFx1YmE3MCwgXHVjNzc0IFx1YWNiZFx1Yjg1Y1x1YzVkMCBcdWM0ZjBcdWM1ZWMgXHVjNzg4XHViMjk0IFx1YWUwMFx1Yzc5MFx1Yjk3YyBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjODAxXHVjNWM4XHVjNzQ0IFx1YjU0YyBcdWIyZThcdWM1YjRcdWM2NDAgXHVjNzdjXHVjZTU4XHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+XHViNjEwXHVkNTVjLCBcdWFjYmRcdWI4NWMgXHVjMGMxXHVjNzU4IFx1YmFhOFx1YjRlMCBcdWM4MTVcdWM4MTBcdWM3NDAgXHVjNTQ0XHViNzk4XHVjNjQwIFx1YWMxOVx1Yzc0MCBcdWIxMjQgXHVhYzAwXHVjOWMwIFx1Yzg3MFx1YWM3NFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD4xLiBcdWNjYWIgXHVjODE1XHVjODEwXHVjNzU4IGluLWRlZ3JlZVx1YjI5NCAwXHVjNzc0XHViMmU0LjxiciBcLz5cclxuMi4gXHViMmU0XHVjNzRjIEstMVx1YWMxYyBcdWM4MTVcdWM4MTBcdWM3NTggaW4tZGVncmVlXHViMjk0IDFcdWM3NzRcdWIyZTQuPGJyIFwvPlxyXG4zLiBcdWIyZTRcdWM3NGMgSy0xXHVhYzFjIFx1YzgxNVx1YzgxMFx1Yzc1OCBvdXQtZGVncmVlXHViMjk0IDFcdWM3NzRcdWIyZTQuPGJyIFwvPlxyXG40LiBcdWI5YzhcdWM5YzBcdWI5YzkgXHVjODE1XHVjODEwXHVjNzU4IG91dC1kZWdyZWVcdWIyOTQgMFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzA0XHVjNzU4IFx1Yzg3MFx1YWM3NFx1Yzc0MCBcdWFjYmRcdWI4NWNcdWIyOTQgXHVjY2FiIEtcdWFjMWMgXHVhZTAwXHVjNzkwXHVjNWQwXHVjMTFjIFx1YjA5OFx1YjIwNFx1YzViNFx1YzljOCBcdWMyMTggXHVjNzg4XHVhY2UwLCBcdWI5YzhcdWM5YzBcdWI5YzkgS1x1YWMxYyBcdWFlMDBcdWM3OTBcdWM1ZDBcdWMxMWMgXHViOWNjXHViMGEwIFx1YzIxOCBcdWM3ODhcdWM3NGNcdWM3NDQgXHVjNzU4XHViYmY4XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZThcdWM1YjQgTlx1YWMxY1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NFx1YjU0YywgXHVjODE1XHVjODEwXHVjNzU4IFx1YzIxOFx1YWMwMCBcdWFjMDBcdWM3YTUgXHVjODAxXHVjNzQwIFx1Y2Y1NFx1Y2Y1NFx1YzJhNFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG5cclxuPHA+XHVjNTQ0XHViNzk4IFx1YWRmOFx1YjliY1x1Yzc0MCBcdWM2MDhcdWM4MWNcdWI5N2MgXHVjODE1XHVjODEwXHVjNzU4IFx1YzIxOFx1YWMwMCBcdWFjMDBcdWM3YTUgXHVjODAxXHVjNzQwIFx1Y2Y1NFx1Y2Y1NFx1YzJhNFx1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYjggXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2tva28xLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjIwMHB4OyB3aWR0aDo0OTFweFwiIFwvPjxcL3A+XHJcblxyXG48cD5cdWM1NDRcdWI3OTggXHVhZGY4XHViNzk4XHVkNTA0XHViMjk0IFx1YzcwNFx1Yzc1OCBcdWFkZjhcdWI3OThcdWQ1MDRcdWJjZjRcdWIyZTQgXHVjODE1XHVjODEwXHVjNzU4IFx1YzIxOFx1YWMwMCBcdWM4MDFcdWM5YzBcdWI5Y2MsIFx1Y2Y1NFx1Y2Y1NFx1YzJhNFx1YWMwMCBcdWM1NDRcdWIyYzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wva29rbzIucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjAzcHg7IHdpZHRoOjQ5M3B4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YzcwNFx1Yzc1OCBcdWFkZjhcdWI3OThcdWQ1MDRcdWFjMDAgXHVjZjU0XHVjZjU0XHVjMmE0XHVhYzAwIFx1YzU0NFx1YjJjYyBcdWM3NzRcdWM3MjBcdWIyOTQgNFx1YmM4OFx1YzlmOCBcdWFlMDBcdWM3OTAgRFx1YzVkMFx1YzExYyBcdWFjYmRcdWI4NWNcdWFjMDAgXHViOWNjXHViMDk4XHVhY2UwLCA2XHViYzg4XHVjOWY4IFx1YWUwMFx1Yzc5MCBFXHVjNWQwXHVjMTFjIFx1YWNiZFx1Yjg1Y1x1YWMwMCBcdWFjMDhcdWI3N2NcdWM4MzggXHViYjM4XHVjODFjXHVjNzU4IFx1Yzg3MFx1YWM3NFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NThcdWM5YzAgXHVjNTRhXHVhZTMwIFx1YjU0Y1x1YmIzOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgTlx1YWNmYyBLXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBOICZsZTsgMTAsMDAwLCAxICZsZTsgSyAmbGU7IDEwMCk8XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIE5cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YzU0Y1x1ZDMwY1x1YmNiMyBcdWIzMDBcdWJiMzhcdWM3OTBcdWI4NWNcdWI5Y2MgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YjJlOFx1YzViNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM4MTVcdWM4MTBcdWM3NTggXHVjMjE4XHVhYzAwIFx1YWMwMFx1YzdhNSBcdWM4MDFcdWM3NDAgXHVjZjU0XHVjZjU0XHVjMmE0XHVjNzU4IFx1YzgxNVx1YzgxMFx1Yzc1OCBcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjMxNzgiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJrb2tvcyIsImRlc2NyaXB0aW9uIjoiPHA+QSBzZXQgb2YgTiB3b3JkcyBpcyBnaXZlbiB3aXRoIHRoZSBsZW5ndGggb2YgZWFjaCB3b3JkIGJlaW5nIGV4YWN0bHkgMksgY2hhcmFjdGVycy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+QSBkaXJlY3RlZCBncmFwaCB3aXRoIGVhY2ggdmVydGV4IGNvbnRhaW5pbmcgYSBzaW5nbGUgbGV0dGVyIGlzIGNhbGxlZCBhICZxdW90O2tva29zJnF1b3Q7IGlmLCBmb3IgZWFjaCB3b3JkIGluIHRoZSBzZXQsIHRoZXJlIGV4aXN0cyBhIGRpcmVjdGVkIHBhdGggaW4gdGhlIGdyYXBoIHN1Y2ggdGhhdCB0aGUgbGFiZWxzIG9uIHRoZSB2ZXJ0aWNlcyBhbG9uZyB0aGF0IHBhdGggZm9ybSB0aGUgd29yZC4gQWRkaXRpb25hbGx5LCBmb3IgYWxsIHZlcnRpY2VzIG9uIHRoYXQgcGF0aCB0aGUgZm9sbG93aW5nIGNvbmRpdGlvbnMgaGF2ZSB0byBiZSBzYXRpc2ZpZWQ6Jm5ic3A7PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+dGhlIGluLWRlZ3JlZSBvZiB0aGUgZmlyc3QgdmVydGV4IGlzIDAmbmJzcDs8XC9saT5cclxuXHQ8bGk+dGhlIGluLWRlZ3JlZXMgb2YgdGhlIG5leHQgSy0xIHZlcnRpY2VzIGlzIDEmbmJzcDs8XC9saT5cclxuXHQ8bGk+dGhlIG91dC1kZWdyZWVzIG9mIHRoZSBuZXh0IEstMSB2ZXJ0aWNlcyBpcyAxJm5ic3A7PFwvbGk+XHJcblx0PGxpPnRoZSBvdXQtZGVncmVlIG9mIHRoZSBsYXN0IHZlcnRleCBpcyAwJm5ic3A7PFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+SW4gb3RoZXIgd29yZHMsIHBhdGhzIGNhbiBmb3JrIG9ubHkgb24gdGhlIGZpcnN0IEsgbGV0dGVycywgYW5kIHRoZXkgY2FuIG1lZXQgb25seSBvbiB0aGUgbGFzdCBLIGxldHRlcnMuPFwvcD5cclxuXHJcbjxwPkZvciB0aGUgZ2l2ZW4gc2V0IG9mIHRoZSB3b3Jkcywgd2Ugc2F5IHRoYXQgdGhlICZxdW90O2tva29zJnF1b3Q7IGlzIG1pbmltYWwgaWYgdGhlIHRvdGFsIG51bWJlciBvZiB2ZXJ0aWNlcyBpcyBhcyBzbWFsbCBhcyBwb3NzaWJsZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQgd2lsbCBmaW5kIHRoZSBudW1iZXIgb2YgdmVydGljZXMgaW4gYSBtaW5pbWFsIGtva29zLiZuYnNwOzxcL3A+XHJcblxyXG48cD5BbiBleGFtcGxlIG9mIGEgbWluaW1hbCBrb2tvcyAodGhlIHNldCBvZiB0aGUgd29yZHMgaXMgZnJvbSB0aGUgdGhpcmQgZXhhbXBsZSk6PFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wva29rbzEucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjAwcHg7IHdpZHRoOjQ5MXB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPkl0IG1heSBzZWVtIHRoYXQgd2UgY2FuIGNvbXBhY3QgdGhlIGdyYXBoIGxpa2UgdGhpczo8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9rb2tvMi5wbmdcIiBzdHlsZT1cImhlaWdodDoyMDNweDsgd2lkdGg6NDkzcHhcIiBcLz48XC9wPlxyXG5cclxuPHA+SG93ZXZlciwgdGhpcyBncmFwaCBpcyBub3QgYSBrb2tvcyBiZWNhdXNlIHBhdGhzIG1lZXQgb24gdGhlIDR0aCBsZXR0ZXIgKEQpLCBhbmQgdGhleSBmb3JrIG9uIHRoZSA2dGggbGV0dGVyIChFKS4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHR3byBpbnRlZ2VycyBOIGFuZCBLLCAxICZsZTsgTiAmbGU7IDEwIDAwMCwgMSAmbGU7IEsgJmxlOyAxMDAuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkVhY2ggb2YgdGhlIGZvbGxvd2luZyBOIGxpbmVzIGNvbnRhaW5zIG9uZSB3b3JkIGZyb20gdGhlIHNldC4gQWxsIGxldHRlcnMgd2lsbCBiZSB1cHBlcmNhc2UgbGV0dGVycyBvZiB0aGUgRW5nbGlzaCBhbHBoYWJldCAoJiMzOTtBJiMzOTstJiMzOTtaJiMzOTspLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBmaXJzdCBhbmQgb25seSBsaW5lIG9mIG91dHB1dCBzaG91bGQgY29udGFpbiB0aGUgbnVtYmVyIG9mIHZlcnRpY2VzIGluIGEgbWluaW1hbCBrb2tvcy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=