시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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+XHJcblxyXG48cD5cdWNmNTRcdWNmNTRcdWMyYTRcdWIyOTQgXHVhZTAwXHVjNzkwIFx1ZDU1OFx1YjA5OFx1Yjk3YyBcdWQzZWNcdWQ1NjhcdWQ1NThcdWFjZTAgXHVjNzg4XHViMjk0IFx1YzgxNVx1YzgxMFx1YzczY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHVjNzIwXHVkNWE1IFx1YWRmOFx1Yjc5OFx1ZDUwNChEaXJlY3RlZCBncmFwaClcdWI5N2MgXHViOWQwXHVkNTVjXHViMmU0LiBcdWM3NzQgXHViNTRjLCBcdWJhYThcdWI0ZTAgXHViMmU4XHVjNWI0XHViMjk0IFx1YWRmOFx1Yjc5OFx1ZDUwNCBcdWMwYzFcdWM3NTggXHVhY2JkXHViODVjXHVhYzAwIFx1Yzg3NFx1YzdhY1x1ZDU3NFx1YzU3YyBcdWQ1NThcdWJhNzAsIFx1Yzc3NCBcdWFjYmRcdWI4NWNcdWM1ZDAgXHVjMzY4IFx1Yzc4OFx1YjI5NCBcdWFlMDBcdWM3OTBcdWI5N2MgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YzgwMVx1YzVjOFx1Yzc0NCBcdWI1NGMgXHViMmU4XHVjNWI0XHVjNjQwIFx1Yzc3Y1x1Y2U1OFx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlx1YjYxMFx1ZDU1YywgXHVhY2JkXHViODVjIFx1YzBjMVx1Yzc1OCBcdWJhYThcdWI0ZTAgXHVjODE1XHVjODEwXHVjNzQwIFx1YzU0NFx1Yjc5OFx1YzY0MCBcdWFjMTlcdWM3NDAgXHViMTI0IFx1YWMwMFx1YzljMCBcdWM4NzBcdWFjNzRcdWM3NDQgXHViOWNjXHVjODcxXHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+MS4gXHVjY2FiIFx1YzgxNVx1YzgxMFx1Yzc1OCBpbi1kZWdyZWVcdWIyOTQgMFx1Yzc3NFx1YjJlNC48YnIgXC8+XHJcbjIuIFx1YjJlNFx1Yzc0YyBLLTFcdWFjMWMgXHVjODE1XHVjODEwXHVjNzU4IGluLWRlZ3JlZVx1YjI5NCAxXHVjNzc0XHViMmU0LjxiciBcLz5cclxuMy4gXHViMmU0XHVjNzRjIEstMVx1YWMxYyBcdWM4MTVcdWM4MTBcdWM3NTggb3V0LWRlZ3JlZVx1YjI5NCAxXHVjNzc0XHViMmU0LjxiciBcLz5cclxuNC4gXHViOWM4XHVjOWMwXHViOWM5IFx1YzgxNVx1YzgxMFx1Yzc1OCBvdXQtZGVncmVlXHViMjk0IDBcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzcwNFx1Yzc1OCBcdWM4NzBcdWFjNzRcdWM3NDAgXHVhY2JkXHViODVjXHViMjk0IFx1Y2NhYiBLXHVhYzFjIFx1YWUwMFx1Yzc5MFx1YzVkMFx1YzExYyBcdWIwOThcdWIyMDRcdWM1YjRcdWM5YzggXHVjMjE4IFx1Yzc4OFx1YWNlMCwgXHViOWM4XHVjOWMwXHViOWM5IEtcdWFjMWMgXHVhZTAwXHVjNzkwXHVjNWQwXHVjMTFjIFx1YjljY1x1YjBhMCBcdWMyMTggXHVjNzg4XHVjNzRjXHVjNzQ0IFx1Yzc1OFx1YmJmOFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMmU4XHVjNWI0IE5cdWFjMWNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzQgXHViNTRjLCBcdWM4MTVcdWM4MTBcdWM3NTggXHVjMjE4XHVhYzAwIFx1YWMwMFx1YzdhNSBcdWM4MDFcdWM3NDAgXHVjZjU0XHVjZjU0XHVjMmE0XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcblxyXG48cD5cdWM1NDRcdWI3OTggXHVhZGY4XHViOWJjXHVjNzQwIFx1YzYwOFx1YzgxY1x1Yjk3YyBcdWM4MTVcdWM4MTBcdWM3NTggXHVjMjE4XHVhYzAwIFx1YWMwMFx1YzdhNSBcdWM4MDFcdWM3NDAgXHVjZjU0XHVjZjU0XHVjMmE0XHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiOCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wva29rbzEucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjAwcHg7IHdpZHRoOjQ5MXB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YzU0NFx1Yjc5OCBcdWFkZjhcdWI3OThcdWQ1MDRcdWIyOTQgXHVjNzA0XHVjNzU4IFx1YWRmOFx1Yjc5OFx1ZDUwNFx1YmNmNFx1YjJlNCBcdWM4MTVcdWM4MTBcdWM3NTggXHVjMjE4XHVhYzAwIFx1YzgwMVx1YzljMFx1YjljYywgXHVjZjU0XHVjZjU0XHVjMmE0XHVhYzAwIFx1YzU0NFx1YjJjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9rb2tvMi5wbmdcIiBzdHlsZT1cImhlaWdodDoyMDNweDsgd2lkdGg6NDkzcHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVjNzA0XHVjNzU4IFx1YWRmOFx1Yjc5OFx1ZDUwNFx1YWMwMCBcdWNmNTRcdWNmNTRcdWMyYTRcdWFjMDAgXHVjNTQ0XHViMmNjIFx1Yzc3NFx1YzcyMFx1YjI5NCA0XHViYzg4XHVjOWY4IFx1YWUwMFx1Yzc5MCBEXHVjNWQwXHVjMTFjIFx1YWNiZFx1Yjg1Y1x1YWMwMCBcdWI5Y2NcdWIwOThcdWFjZTAsIDZcdWJjODhcdWM5ZjggXHVhZTAwXHVjNzkwIEVcdWM1ZDBcdWMxMWMgXHVhY2JkXHViODVjXHVhYzAwIFx1YWMwOFx1Yjc3Y1x1YzgzOCBcdWJiMzhcdWM4MWNcdWM3NTggXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YzljMCBcdWM1NGFcdWFlMzAgXHViNTRjXHViYjM4XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBOXHVhY2ZjIEtcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IE4gJmxlOyAxMCwwMDAsIDEgJmxlOyBLICZsZTsgMTAwKTxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgTlx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjNTRjXHVkMzBjXHViY2IzIFx1YjMwMFx1YmIzOFx1Yzc5MFx1Yjg1Y1x1YjljYyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHViMmU4XHVjNWI0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzgxNVx1YzgxMFx1Yzc1OCBcdWMyMThcdWFjMDAgXHVhYzAwXHVjN2E1IFx1YzgwMVx1Yzc0MCBcdWNmNTRcdWNmNTRcdWMyYTRcdWM3NTggXHVjODE1XHVjODEwXHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzE3OCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Imtva29zIiwiZGVzY3JpcHRpb24iOiI8cD5BIHNldCBvZiBOIHdvcmRzIGlzIGdpdmVuIHdpdGggdGhlIGxlbmd0aCBvZiBlYWNoIHdvcmQgYmVpbmcgZXhhY3RseSAySyBjaGFyYWN0ZXJzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5BIGRpcmVjdGVkIGdyYXBoIHdpdGggZWFjaCB2ZXJ0ZXggY29udGFpbmluZyBhIHNpbmdsZSBsZXR0ZXIgaXMgY2FsbGVkIGEgJnF1b3Q7a29rb3MmcXVvdDsgaWYsIGZvciBlYWNoIHdvcmQgaW4gdGhlIHNldCwgdGhlcmUgZXhpc3RzIGEgZGlyZWN0ZWQgcGF0aCBpbiB0aGUgZ3JhcGggc3VjaCB0aGF0IHRoZSBsYWJlbHMgb24gdGhlIHZlcnRpY2VzIGFsb25nIHRoYXQgcGF0aCBmb3JtIHRoZSB3b3JkLiBBZGRpdGlvbmFsbHksIGZvciBhbGwgdmVydGljZXMgb24gdGhhdCBwYXRoIHRoZSBmb2xsb3dpbmcgY29uZGl0aW9ucyBoYXZlIHRvIGJlIHNhdGlzZmllZDombmJzcDs8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT50aGUgaW4tZGVncmVlIG9mIHRoZSBmaXJzdCB2ZXJ0ZXggaXMgMCZuYnNwOzxcL2xpPlxyXG5cdDxsaT50aGUgaW4tZGVncmVlcyBvZiB0aGUgbmV4dCBLLTEgdmVydGljZXMgaXMgMSZuYnNwOzxcL2xpPlxyXG5cdDxsaT50aGUgb3V0LWRlZ3JlZXMgb2YgdGhlIG5leHQgSy0xIHZlcnRpY2VzIGlzIDEmbmJzcDs8XC9saT5cclxuXHQ8bGk+dGhlIG91dC1kZWdyZWUgb2YgdGhlIGxhc3QgdmVydGV4IGlzIDAmbmJzcDs8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5JbiBvdGhlciB3b3JkcywgcGF0aHMgY2FuIGZvcmsgb25seSBvbiB0aGUgZmlyc3QgSyBsZXR0ZXJzLCBhbmQgdGhleSBjYW4gbWVldCBvbmx5IG9uIHRoZSBsYXN0IEsgbGV0dGVycy48XC9wPlxyXG5cclxuPHA+Rm9yIHRoZSBnaXZlbiBzZXQgb2YgdGhlIHdvcmRzLCB3ZSBzYXkgdGhhdCB0aGUgJnF1b3Q7a29rb3MmcXVvdDsgaXMgbWluaW1hbCBpZiB0aGUgdG90YWwgbnVtYmVyIG9mIHZlcnRpY2VzIGlzIGFzIHNtYWxsIGFzIHBvc3NpYmxlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdGhhdCB3aWxsIGZpbmQgdGhlIG51bWJlciBvZiB2ZXJ0aWNlcyBpbiBhIG1pbmltYWwga29rb3MuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkFuIGV4YW1wbGUgb2YgYSBtaW5pbWFsIGtva29zICh0aGUgc2V0IG9mIHRoZSB3b3JkcyBpcyBmcm9tIHRoZSB0aGlyZCBleGFtcGxlKTo8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9rb2tvMS5wbmdcIiBzdHlsZT1cImhlaWdodDoyMDBweDsgd2lkdGg6NDkxcHhcIiBcLz48XC9wPlxyXG5cclxuPHA+SXQgbWF5IHNlZW0gdGhhdCB3ZSBjYW4gY29tcGFjdCB0aGUgZ3JhcGggbGlrZSB0aGlzOjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2tva28yLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjIwM3B4OyB3aWR0aDo0OTNweFwiIFwvPjxcL3A+XHJcblxyXG48cD5Ib3dldmVyLCB0aGlzIGdyYXBoIGlzIG5vdCBhIGtva29zIGJlY2F1c2UgcGF0aHMgbWVldCBvbiB0aGUgNHRoIGxldHRlciAoRCksIGFuZCB0aGV5IGZvcmsgb24gdGhlIDZ0aCBsZXR0ZXIgKEUpLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdHdvIGludGVnZXJzIE4gYW5kIEssIDEgJmxlOyBOICZsZTsgMTAgMDAwLCAxICZsZTsgSyAmbGU7IDEwMC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgZm9sbG93aW5nIE4gbGluZXMgY29udGFpbnMgb25lIHdvcmQgZnJvbSB0aGUgc2V0LiBBbGwgbGV0dGVycyB3aWxsIGJlIHVwcGVyY2FzZSBsZXR0ZXJzIG9mIHRoZSBFbmdsaXNoIGFscGhhYmV0ICgmIzM5O0EmIzM5Oy0mIzM5O1omIzM5OykuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGZpcnN0IGFuZCBvbmx5IGxpbmUgb2Ygb3V0cHV0IHNob3VsZCBjb250YWluIHRoZSBudW1iZXIgb2YgdmVydGljZXMgaW4gYSBtaW5pbWFsIGtva29zLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==