시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 131 32 26 23.636%

문제

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+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzE3OCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Imtva29zIiwiZGVzY3JpcHRpb24iOiI8cD5BIHNldCBvZiBOIHdvcmRzIGlzIGdpdmVuIHdpdGggdGhlIGxlbmd0aCBvZiBlYWNoIHdvcmQgYmVpbmcgZXhhY3RseSAySyBjaGFyYWN0ZXJzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5BIGRpcmVjdGVkIGdyYXBoIHdpdGggZWFjaCB2ZXJ0ZXggY29udGFpbmluZyBhIHNpbmdsZSBsZXR0ZXIgaXMgY2FsbGVkIGEgJnF1b3Q7a29rb3MmcXVvdDsgaWYsIGZvciBlYWNoIHdvcmQgaW4gdGhlIHNldCwgdGhlcmUgZXhpc3RzIGEgZGlyZWN0ZWQgcGF0aCBpbiB0aGUgZ3JhcGggc3VjaCB0aGF0IHRoZSBsYWJlbHMgb24gdGhlIHZlcnRpY2VzIGFsb25nIHRoYXQgcGF0aCBmb3JtIHRoZSB3b3JkLiBBZGRpdGlvbmFsbHksIGZvciBhbGwgdmVydGljZXMgb24gdGhhdCBwYXRoIHRoZSBmb2xsb3dpbmcgY29uZGl0aW9ucyBoYXZlIHRvIGJlIHNhdGlzZmllZDombmJzcDs8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT50aGUgaW4tZGVncmVlIG9mIHRoZSBmaXJzdCB2ZXJ0ZXggaXMgMCZuYnNwOzxcL2xpPlxyXG5cdDxsaT50aGUgaW4tZGVncmVlcyBvZiB0aGUgbmV4dCBLLTEgdmVydGljZXMgaXMgMSZuYnNwOzxcL2xpPlxyXG5cdDxsaT50aGUgb3V0LWRlZ3JlZXMgb2YgdGhlIG5leHQgSy0xIHZlcnRpY2VzIGlzIDEmbmJzcDs8XC9saT5cclxuXHQ8bGk+dGhlIG91dC1kZWdyZWUgb2YgdGhlIGxhc3QgdmVydGV4IGlzIDAmbmJzcDs8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5JbiBvdGhlciB3b3JkcywgcGF0aHMgY2FuIGZvcmsgb25seSBvbiB0aGUgZmlyc3QgSyBsZXR0ZXJzLCBhbmQgdGhleSBjYW4gbWVldCBvbmx5IG9uIHRoZSBsYXN0IEsgbGV0dGVycy48XC9wPlxyXG5cclxuPHA+Rm9yIHRoZSBnaXZlbiBzZXQgb2YgdGhlIHdvcmRzLCB3ZSBzYXkgdGhhdCB0aGUgJnF1b3Q7a29rb3MmcXVvdDsgaXMgbWluaW1hbCBpZiB0aGUgdG90YWwgbnVtYmVyIG9mIHZlcnRpY2VzIGlzIGFzIHNtYWxsIGFzIHBvc3NpYmxlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdGhhdCB3aWxsIGZpbmQgdGhlIG51bWJlciBvZiB2ZXJ0aWNlcyBpbiBhIG1pbmltYWwga29rb3MuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkFuIGV4YW1wbGUgb2YgYSBtaW5pbWFsIGtva29zICh0aGUgc2V0IG9mIHRoZSB3b3JkcyBpcyBmcm9tIHRoZSB0aGlyZCBleGFtcGxlKTo8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9rb2tvMS5wbmdcIiBzdHlsZT1cImhlaWdodDoyMDBweDsgd2lkdGg6NDkxcHhcIiBcLz48XC9wPlxyXG5cclxuPHA+SXQgbWF5IHNlZW0gdGhhdCB3ZSBjYW4gY29tcGFjdCB0aGUgZ3JhcGggbGlrZSB0aGlzOjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2tva28yLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjIwM3B4OyB3aWR0aDo0OTNweFwiIFwvPjxcL3A+XHJcblxyXG48cD5Ib3dldmVyLCB0aGlzIGdyYXBoIGlzIG5vdCBhIGtva29zIGJlY2F1c2UgcGF0aHMgbWVldCBvbiB0aGUgNHRoIGxldHRlciAoRCksIGFuZCB0aGV5IGZvcmsgb24gdGhlIDZ0aCBsZXR0ZXIgKEUpLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdHdvIGludGVnZXJzIE4gYW5kIEssIDEgJmxlOyBOICZsZTsgMTAgMDAwLCAxICZsZTsgSyAmbGU7IDEwMC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgZm9sbG93aW5nIE4gbGluZXMgY29udGFpbnMgb25lIHdvcmQgZnJvbSB0aGUgc2V0LiBBbGwgbGV0dGVycyB3aWxsIGJlIHVwcGVyY2FzZSBsZXR0ZXJzIG9mIHRoZSBFbmdsaXNoIGFscGhhYmV0ICgmIzM5O0EmIzM5Oy0mIzM5O1omIzM5OykuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGZpcnN0IGFuZCBvbmx5IGxpbmUgb2Ygb3V0cHV0IHNob3VsZCBjb250YWluIHRoZSBudW1iZXIgb2YgdmVydGljZXMgaW4gYSBtaW5pbWFsIGtva29zLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d