문제
지난 대회에 이어 이번에도 문자열 문제를 출제하고 싶은 에릭은 다음과 같은 문제를 떠올렸다. 정답 코드를 짜기 귀찮은 에릭을 위해 대신 문제를 풀어주자!
- 길이가 $M$인 $N$개의 문자열 $S_1, S_2, \cdots, S_N$이 주어진다.
- 다음 방법으로 만들 수 있는 문자열 $T$ 중 사전순으로 가장 앞에 오는 것을 출력한다.
- $S_1, S_2, \cdots, S_N$ 중 $K$개를 선택한 후, 이어 붙여서 길이 $K \cdot M$의 문자열을 만든다.
- 이렇게 얻은 $K \cdot M$개의 문자를 적당히 재배치하여 문자열 $T$를 만든다.
서로 다른 두 문자열 $a,ドル $b$에 대해 다음 중 하나가 성립할 때 문자열 $a$가 문자열 $b$보다 사전순으로 앞에 온다고 말한다.
- $a$가 $b$의 접두사
- $a$와 $b$가 달라지는 첫 위치에서 $a$의 문자가 알파벳 순으로 $b$의 문자보다 앞에 위치함
출력
$S_1, S_2, \cdots, S_N$을 이용하여 위에서 설명한 방법으로 만들 수 있는 문자열 $T$ 중 사전순으로 가장 앞에 오는 것을 출력한다.
제한
- 1ドル \le K \le N \le 300$
- 1ドル \le M \le 300$
- $S_i$는 영어 대문자로 구성된 길이 $M$의 문자열 $(1 \le i \le N)$
서브태스크
| 번호 | 배점 | 제한 | | 1 | 15 | $M = 1$
|
| 2 | 20 | $S_1 = S_2 = \cdots = S_N$
|
| 3 | 65 | 추가 제약 조건 없음
|
W3sicHJvYmxlbV9pZCI6IjI5MTk4IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjNzc0XHViYzg4XHVjNWQwXHViMjk0IENcdWJjODhcdWM3NzQgXHViYjM4XHVjNzkwXHVjNWY0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWM5YzBcdWIwOWMgXHViMzAwXHVkNjhjXHVjNWQwIFx1Yzc3NFx1YzViNCBcdWM3NzRcdWJjODhcdWM1ZDBcdWIzYzQgXHViYjM4XHVjNzkwXHVjNWY0IFx1YmIzOFx1YzgxY1x1Yjk3YyBcdWNkOWNcdWM4MWNcdWQ1NThcdWFjZTAgXHVjMmY2XHVjNzQwIFx1YzVkMFx1YjlhZFx1Yzc0MCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1YmIzOFx1YzgxY1x1Yjk3YyBcdWI1YTBcdWM2MmNcdWI4MzhcdWIyZTQuIFx1YzgxNVx1YjJmNSBcdWNmNTRcdWI0ZGNcdWI5N2MgXHVjOWRjXHVhZTMwIFx1YWRjMFx1Y2MyZVx1Yzc0MCBcdWM1ZDBcdWI5YWRcdWM3NDQgXHVjNzA0XHVkNTc0IFx1YjMwMFx1YzJlMCBcdWJiMzhcdWM4MWNcdWI5N2MgXHVkNDgwXHVjNWI0XHVjOGZjXHVjNzkwITxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlx1YWUzOFx1Yzc3NFx1YWMwMCAkTSRcdWM3NzggJE4kXHVhYzFjXHVjNzU4IFx1YmIzOFx1Yzc5MFx1YzVmNCAkU18xLCBTXzIsIFxcY2RvdHMsIFNfTiRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWIyZTRcdWM3NGMgXHViYzI5XHViYzk1XHVjNzNjXHViODVjIFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YmIzOFx1Yzc5MFx1YzVmNCAkVCQgXHVjOTExIDxzdHJvbmc+XHVjMGFjXHVjODA0XHVjMjFjXHVjNzNjXHViODVjIFx1YWMwMFx1YzdhNSBcdWM1NWU8XC9zdHJvbmc+XHVjNWQwIFx1YzYyNFx1YjI5NCBcdWFjODNcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LlxyXG5cdDxvbD5cclxuXHRcdDxsaT4kU18xLCBTXzIsIFxcY2RvdHMsIFNfTiQgXHVjOTExICRLJFx1YWMxY1x1Yjk3YyBcdWMxMjBcdWQwZGRcdWQ1NWMgXHVkNmM0LCBcdWM3NzRcdWM1YjQgXHViZDk5XHVjNWVjXHVjMTFjIFx1YWUzOFx1Yzc3NCAkSyBcXGNkb3QgTSRcdWM3NTggXHViYjM4XHVjNzkwXHVjNWY0XHVjNzQ0IFx1YjljY1x1YjRlMFx1YjJlNC48XC9saT5cclxuXHRcdDxsaT5cdWM3NzRcdWI4MDdcdWFjOGMgXHVjNWJiXHVjNzQwICRLIFxcY2RvdCBNJFx1YWMxY1x1Yzc1OCBcdWJiMzhcdWM3OTBcdWI5N2MgXHVjODAxXHViMmY5XHVkNzg4IFx1YzdhY1x1YmMzMFx1Y2U1OFx1ZDU1OFx1YzVlYyBcdWJiMzhcdWM3OTBcdWM1ZjQgJFQkXHViOTdjIFx1YjljY1x1YjRlMFx1YjJlNC48XC9saT5cclxuXHQ8XC9vbD5cclxuXHQ8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1YjQ1MCBcdWJiMzhcdWM3OTBcdWM1ZjQgJGEkLCAkYiRcdWM1ZDAgXHViMzAwXHVkNTc0IFx1YjJlNFx1Yzc0YyBcdWM5MTEgXHVkNTU4XHViMDk4XHVhYzAwIFx1YzEzMVx1YjliZFx1ZDU2MCBcdWI1NGMgXHViYjM4XHVjNzkwXHVjNWY0ICRhJFx1YWMwMCBcdWJiMzhcdWM3OTBcdWM1ZjQgJGIkXHViY2Y0XHViMmU0IFx1YzBhY1x1YzgwNFx1YzIxY1x1YzczY1x1Yjg1YyBcdWM1NWVcdWM1ZDAgXHVjNjI4XHViMmU0XHVhY2UwIFx1YjlkMFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT4kYSRcdWFjMDAgJGIkXHVjNzU4IFx1YzgxMVx1YjQ1MFx1YzBhYzxcL2xpPlxyXG5cdDxsaT4kYSRcdWM2NDAgJGIkXHVhYzAwIFx1YjJlY1x1Yjc3Y1x1YzljMFx1YjI5NCBcdWNjYWIgXHVjNzA0XHVjZTU4XHVjNWQwXHVjMTFjICRhJFx1Yzc1OCBcdWJiMzhcdWM3OTBcdWFjMDAgXHVjNTRjXHVkMzBjXHViY2IzIFx1YzIxY1x1YzczY1x1Yjg1YyAkYiRcdWM3NTggXHViYjM4XHVjNzkwXHViY2Y0XHViMmU0IFx1YzU1ZVx1YzVkMCBcdWM3MDRcdWNlNThcdWQ1Njg8XC9saT5cclxuPFwvdWw+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjMTM4IFx1YzgxNVx1YzIxOCAkTiQsICRNJCwgJEskXHVhYzAwIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD4kaSArIDEkXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWJiMzhcdWM3OTBcdWM1ZjQgJFNfaSRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAkKDEgXFxsZSBpIFxcbGUgTikkPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+JFNfMSwgU18yLCBcXGNkb3RzLCBTX04kXHVjNzQ0IFx1Yzc3NFx1YzZhOVx1ZDU1OFx1YzVlYyBcdWM3MDRcdWM1ZDBcdWMxMWMgXHVjMTI0XHViYTg1XHVkNTVjIFx1YmMyOVx1YmM5NVx1YzczY1x1Yjg1YyBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWJiMzhcdWM3OTBcdWM1ZjQgJFQkIFx1YzkxMSA8c3Ryb25nPlx1YzBhY1x1YzgwNFx1YzIxY1x1YzczY1x1Yjg1YyBcdWFjMDBcdWM3YTUgXHVjNTVlPFwvc3Ryb25nPlx1YzVkMCBcdWM2MjRcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4iLCJsaW1pdCI6Ijx1bD5cclxuXHQ8bGk+JDEgXFxsZSBLIFxcbGUgTiBcXGxlIDMwMCQ8XC9saT5cclxuXHQ8bGk+JDEgXFxsZSBNIFxcbGUgMzAwJDxcL2xpPlxyXG5cdDxsaT4kU19pJFx1YjI5NCBcdWM2MDFcdWM1YjQgXHViMzAwXHViYjM4XHVjNzkwXHViODVjIFx1YWQ2Y1x1YzEzMVx1YjQxYyBcdWFlMzhcdWM3NzQgJE0kXHVjNzU4IFx1YmIzOFx1Yzc5MFx1YzVmNCAkKDEgXFxsZSBpIFxcbGUgTikkPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJzdWJ0YXNrMSI6IjxwPiRNID0gMSQ8XC9wPlxyXG4iLCJzdWJ0YXNrMiI6IjxwPiRTXzEgPSBTXzIgPSBcXGNkb3RzID0gU19OJDxcL3A+XHJcbiIsInN1YnRhc2szIjoiPHA+XHVjZDk0XHVhYzAwIFx1YzgxY1x1YzU3ZCBcdWM4NzBcdWFjNzQgXHVjNWM2XHVjNzRjPFwvcD5cclxuIn0seyJwcm9ibGVtX2lkIjoiMjkxOTgiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJZZXQgQW5vdGhlciBTdHJpbmcgUHJvYmxlbSBpbiBDIiwiZGVzY3JpcHRpb24iOiI8cD5Gb2xsb3dpbmcgdGhlIHByZXZpb3VzIGNvbnRlc3QsIEVyaWMgYWxzbyB3YW50cyBhIHN0cmluZyBwcm9ibGVtIHRoaXMgdGltZS4gRXJpYyBpcyB0b28gbGF6eSB0byBjb2RlIHRoZSBzb2x1dGlvbi4gQ2FuIHlvdSBzb2x2ZSB0aGUgcHJvYmxlbSBmb3IgaGltPzxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPllvdSBhcmUgZ2l2ZW4gJE4kIHN0cmluZ3MgJFNfMSwgU18yLCBcXGNkb3RzLCBTX04kIG9mIGxlbmd0aCAkTSQuPFwvbGk+XHJcblx0PGxpPlByaW50IHRoZSA8c3Ryb25nPmxleGljb2dyYXBoaWNhbGx5IHNtYWxsZXN0PFwvc3Ryb25nPiZuYnNwO3N0cmluZyAkVCQgdGhhdCBjYW4gYmUgbWFkZSB1c2luZyB0aGUgZm9sbG93aW5nIG1ldGhvZC5cclxuXHQ8b2w+XHJcblx0XHQ8bGk+U2VsZWN0ICRLJCBzdHJpbmdzIGZyb20gJFNfMSwgU18yLCBcXGNkb3RzLCBTX04kIGFuZCBjb25jYXRlbmF0ZSB0aGVtIHRvIGZvcm0gYSBzdHJpbmcgb2YgbGVuZ3RoICRLIFxcY2RvdCBNJC48XC9saT5cclxuXHRcdDxsaT5SZWFycmFuZ2UgdGhlICRLIFxcY2RvdCBNJCBjaGFyYWN0ZXJzIG9idGFpbmVkIGluIHRoZSBwcmV2aW91cyBzdGVwIHRvIGZvcm0gdGhlIHN0cmluZyAkVCQuPFwvbGk+XHJcblx0PFwvb2w+XHJcblx0PFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+Rm9yIHR3byBkaWZmZXJlbnQgc3RyaW5ncyAkYSQgYW5kICRiJCwgc3RyaW5nICRhJCBpcyBsZXhpY29ncmFwaGljYWxseSBzbWFsbGVyIHRoYW4gYSBzdHJpbmcgJGIkIGlmIGFuZCBvbmx5IGlmIG9uZSBvZiB0aGUgZm9sbG93aW5nIGhvbGRzOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPiRhJCBpcyBhIHByZWZpeCBvZiAkYiQ7PFwvbGk+XHJcblx0PGxpPmluIHRoZSBmaXJzdCBwb3NpdGlvbiB3aGVyZSAkYSQgYW5kICRiJCBkaWZmZXIsIHRoZSBzdHJpbmcgJGEkIGhhcyBhIGxldHRlciB0aGF0IGFwcGVhcnMgZWFybGllciBpbiB0aGUgYWxwaGFiZXQgdGhhbiB0aGUgY29ycmVzcG9uZGluZyBsZXR0ZXIgaW4gJGIkLjxcL2xpPlxyXG48XC91bD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyB0aHJlZSBzcGFjZS1zZXBhcmF0ZWQmbmJzcDtpbnRlZ2VycyAkTiQsICRNJCwgYW5kICRLJC48XC9wPlxyXG5cclxuPHA+VGhlICRpICsgMSQtdGggbGluZSBjb250YWlucyBhIHN0cmluZyAkU19pJC4gJCgxIFxcbGUgaSBcXGxlIE4pJDxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlByaW50IHRoZSA8c3Ryb25nPmxleGljb2dyYXBoaWNhbGx5IHNtYWxsZXN0PFwvc3Ryb25nPiZuYnNwO3N0cmluZyAkVCQgdGhhdCBjYW4gYmUgY3JlYXRlZCB1c2luZyAkU18xLCBTXzIsIFxcY2RvdHMsIFNfTiQgYWNjb3JkaW5nIHRvIHRoZSBtZXRob2QgZGVzY3JpYmVkIGFib3ZlLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2giLCJsaW1pdCI6Ijx1bD5cclxuXHQ8bGk+JDEgXFxsZSBLIFxcbGUgTiBcXGxlIDMwMCQ8XC9saT5cclxuXHQ8bGk+JDEgXFxsZSBNIFxcbGUgMzAwJDxcL2xpPlxyXG5cdDxsaT4kU19pJCBpcyBhIHN0cmluZyBvZiAkTSQgdXBwZXJjYXNlIEVuZ2xpc2ggbGV0dGVycyAkKDEgXFxsZSBpIFxcbGUgTikkPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJzdWJ0YXNrMSI6IjxwPiRNID0gMSQ8XC9wPlxyXG4iLCJzdWJ0YXNrMiI6IjxwPiRTXzEgPSBTXzIgPSBcXGNkb3RzID0gU19OJDxcL3A+XHJcbiIsInN1YnRhc2szIjoiPHA+Tm8gYWRkaXRpb25hbCBjb25zdHJhaW50czxcL3A+XHJcbiJ9XQ==