시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 61 40 27 62.791%

문제

슈퍼히어로 박승원은 결국 지구를 침략한 악당 로봇들을 해킹하는 데 성공했다. 로봇은 N개의 취약점을 가지고 있는데, (1 <= N <= 20) i번째 취약점은 'A', 'B', 'C' 로만 구성된 15자 이하의 문자열 Si 로 표현된다. 박승원 역시 로봇들을 'A', 'B', 'C' 버튼을 누르면서 공격할 수 있으며, 로봇의 취약점과 일치하도록 버튼을 누르면 공격에 성공하게 된다.

예를 들어 로봇의 취약점이 "ABA", "CB", "ABACB"라 하자. 박승원이 만약에 "ABACB"를 누르게 되면, 1 ~ 3번째 문자가 "ABA", 4 ~ 5번째 문자가 "CB", 전체가 "ABACB"와 매칭되어서 3번의 공격을 성공한 것과 같다. 이 예제에서 볼수 있다시피 여러개의 취약점을 한꺼번에 공격할 수 있으며, 또한 한 취약점을 여러 번 사용할 수도 있다.

우리의 슈퍼히어로 박승원에게는 시간이 없기 때문에 정확히 K번밖에 버튼을 누를 수 없다. (1 <= K <= 1000) 우리 모두 박승원을 도와 그가 공격할 수 있는 최대 횟수를 출력해주자.

입력

첫 번째 줄에는 N과 K개 주어지며, 이후 N개의 줄에 취약점 Si가 주어진다.

출력

박승원이 공격할 수 있는 최대 횟수를 출력한다.

예제 입력 1

3 7
ABA
CB
ABACB

예제 출력 1

4

힌트

ABACBCB 를 눌러 공격하면 ABA와 한번, ABACB와 한번, CB와 두번 매칭되어 총 4번 공격에 성공한다.

W3sicHJvYmxlbV9pZCI6IjU5MDUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM1NDVcdWIyZjkgXHViODVjXHViZDA3IiwiZGVzY3JpcHRpb24iOiI8cD5cdWMyODhcdWQzN2NcdWQ3ODhcdWM1YjRcdWI4NWMgXHViYzE1XHVjMmI5XHVjNmQwXHVjNzQwIFx1YWNiMFx1YWQ2ZCBcdWM5YzBcdWFkNmNcdWI5N2MgXHVjZTY4XHViN2I1XHVkNTVjIFx1YzU0NVx1YjJmOSBcdWI4NWNcdWJkMDdcdWI0ZTRcdWM3NDQgXHVkNTc0XHVkMGI5XHVkNTU4XHViMjk0IFx1YjM3MCBcdWMxMzFcdWFjZjVcdWQ1ODhcdWIyZTQuIFx1Yjg1Y1x1YmQwN1x1Yzc0MCBOXHVhYzFjXHVjNzU4IFx1Y2RlOFx1YzU3ZFx1YzgxMFx1Yzc0NCBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHViMjk0XHViMzcwLCAoMSAmbHQ7PSBOICZsdDs9IDIwKSBpXHViYzg4XHVjOWY4IFx1Y2RlOFx1YzU3ZFx1YzgxMFx1Yzc0MCAmIzM5O0EmIzM5OywgJiMzOTtCJiMzOTssICYjMzk7QyYjMzk7IFx1Yjg1Y1x1YjljYyBcdWFkNmNcdWMxMzFcdWI0MWMgMTVcdWM3OTAgXHVjNzc0XHVkNTU4XHVjNzU4IFx1YmIzOFx1Yzc5MFx1YzVmNCBTaSBcdWI4NWMgXHVkNDVjXHVkNjA0XHViNDFjXHViMmU0LiBcdWJjMTVcdWMyYjlcdWM2ZDAgXHVjNWVkXHVjMmRjIFx1Yjg1Y1x1YmQwN1x1YjRlNFx1Yzc0NCAmIzM5O0EmIzM5OywgJiMzOTtCJiMzOTssICYjMzk7QyYjMzk7IFx1YmM4NFx1ZDJiY1x1Yzc0NCBcdWIyMDRcdWI5NzRcdWJhNzRcdWMxMWMgXHVhY2Y1XHVhY2E5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1Yjg1Y1x1YmQwN1x1Yzc1OCBcdWNkZThcdWM1N2RcdWM4MTBcdWFjZmMgXHVjNzdjXHVjZTU4XHVkNTU4XHViM2M0XHViODVkIFx1YmM4NFx1ZDJiY1x1Yzc0NCBcdWIyMDRcdWI5NzRcdWJhNzQgXHVhY2Y1XHVhY2E5XHVjNWQwIFx1YzEzMVx1YWNmNVx1ZDU1OFx1YWM4YyBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQgXHViODVjXHViZDA3XHVjNzU4IFx1Y2RlOFx1YzU3ZFx1YzgxMFx1Yzc3NCAmcXVvdDtBQkEmcXVvdDssICZxdW90O0NCJnF1b3Q7LCAmcXVvdDtBQkFDQiZxdW90O1x1Yjc3YyBcdWQ1NThcdWM3OTAuIFx1YmMxNVx1YzJiOVx1YzZkMFx1Yzc3NCBcdWI5Y2NcdWM1N2RcdWM1ZDAgJnF1b3Q7QUJBQ0ImcXVvdDtcdWI5N2MgXHViMjA0XHViOTc0XHVhYzhjIFx1YjQxOFx1YmE3NCwgMSB+IDNcdWJjODhcdWM5ZjggXHViYjM4XHVjNzkwXHVhYzAwICZxdW90O0FCQSZxdW90OywgNCB+IDVcdWJjODhcdWM5ZjggXHViYjM4XHVjNzkwXHVhYzAwICZxdW90O0NCJnF1b3Q7LCBcdWM4MDRcdWNjYjRcdWFjMDAgJnF1b3Q7QUJBQ0ImcXVvdDtcdWM2NDAgXHViOWU0XHVjZTZkXHViNDE4XHVjNWI0XHVjMTFjIDNcdWJjODhcdWM3NTggXHVhY2Y1XHVhY2E5XHVjNzQ0IFx1YzEzMVx1YWNmNVx1ZDU1YyBcdWFjODNcdWFjZmMgXHVhYzE5XHViMmU0LiBcdWM3NzQgXHVjNjA4XHVjODFjXHVjNWQwXHVjMTFjIFx1YmNmY1x1YzIxOCBcdWM3ODhcdWIyZTRcdWMyZGNcdWQ1M2MgXHVjNWVjXHViN2VjXHVhYzFjXHVjNzU4IFx1Y2RlOFx1YzU3ZFx1YzgxMFx1Yzc0NCBcdWQ1NWNcdWFlYmNcdWJjODhcdWM1ZDAgXHVhY2Y1XHVhY2E5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1YjYxMFx1ZDU1YyBcdWQ1NWMgXHVjZGU4XHVjNTdkXHVjODEwXHVjNzQ0IFx1YzVlY1x1YjdlYyBcdWJjODggXHVjMGFjXHVjNmE5XHVkNTYwIFx1YzIxOFx1YjNjNCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzZiMFx1YjlhY1x1Yzc1OCBcdWMyODhcdWQzN2NcdWQ3ODhcdWM1YjRcdWI4NWMgXHViYzE1XHVjMmI5XHVjNmQwXHVjNWQwXHVhYzhjXHViMjk0IFx1YzJkY1x1YWMwNFx1Yzc3NCBcdWM1YzZcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIFx1YzgxNVx1ZDY1NVx1ZDc4OCBLXHViYzg4XHViYzE2XHVjNWQwIFx1YmM4NFx1ZDJiY1x1Yzc0NCBcdWIyMDRcdWI5N2MgXHVjMjE4IFx1YzVjNlx1YjJlNC4gKDEgJmx0Oz0gSyAmbHQ7PSAxMDAwKSBcdWM2YjBcdWI5YWMgXHViYWE4XHViNDUwIFx1YmMxNVx1YzJiOVx1YzZkMFx1Yzc0NCBcdWIzYzRcdWM2NDAgXHVhZGY4XHVhYzAwIFx1YWNmNVx1YWNhOVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1Y2Q1Y1x1YjMwMCBcdWQ2OWZcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTc0XHVjOGZjXHVjNzkwLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHJcblx0XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgTlx1YWNmYyBLXHVhYzFjIFx1YzhmY1x1YzViNFx1YzljMFx1YmE3MCwgXHVjNzc0XHVkNmM0IE5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIFx1Y2RlOFx1YzU3ZFx1YzgxMCBTaVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuXHJcbjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdFx1YmMxNVx1YzJiOVx1YzZkMFx1Yzc3NCBcdWFjZjVcdWFjYTlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWNkNWNcdWIzMDAgXHVkNjlmXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC5cclxuPFwvcD5cclxuIiwiaGludCI6IjxwPlxyXG5cdEFCQUNCQ0IgXHViOTdjIFx1YjIwY1x1YjdlYyBcdWFjZjVcdWFjYTlcdWQ1NThcdWJhNzQgQUJBXHVjNjQwIFx1ZDU1Y1x1YmM4OCwgQUJBQ0JcdWM2NDAgXHVkNTVjXHViYzg4LCBDQlx1YzY0MCBcdWI0NTBcdWJjODggXHViOWU0XHVjZTZkXHViNDE4XHVjNWI0IFx1Y2QxZCA0XHViYzg4IFx1YWNmNVx1YWNhOVx1YzVkMCBcdWMxMzFcdWFjZjVcdWQ1NWNcdWIyZTQuXHJcbjxcL3A+Iiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI1OTA1IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiVmlkZW8gR2FtZSIsImRlc2NyaXB0aW9uIjoiPHA+QmVzc2llIGlzIHBsYXlpbmcgYSB2aWRlbyBnYW1lISBJbiB0aGUgZ2FtZSwgdGhlIHRocmVlIGxldHRlcnMgJmFwb3M7QSZhcG9zOywgJmFwb3M7QiZhcG9zOywgYW5kICZhcG9zO0MmYXBvczsgYXJlIHRoZSBvbmx5IHZhbGlkIGJ1dHRvbnMuIEJlc3NpZSBtYXkgcHJlc3MgdGhlIGJ1dHRvbnMgaW4gYW55IG9yZGVyIHNoZSBsaWtlczsgaG93ZXZlciwgdGhlcmUgYXJlIG9ubHkgTiBkaXN0aW5jdCBjb21ib3MgcG9zc2libGUgKDEgJmx0Oz0gTiAmbHQ7PSAyMCkuIENvbWJvIGkgaXMgcmVwcmVzZW50ZWQgYXMgYSBzdHJpbmcgU19pIHdoaWNoIGhhcyBhIGxlbmd0aCBiZXR3ZWVuIDEgYW5kIDE1IGFuZCBjb250YWlucyBvbmx5IHRoZSBsZXR0ZXJzICZhcG9zO0EmYXBvczssICZhcG9zO0ImYXBvczssIGFuZCAmYXBvcztDJmFwb3M7LjxcL3A+PHA+V2hlbmV2ZXIgQmVzc2llIHByZXNzZXMgYSBjb21iaW5hdGlvbiBvZiBsZXR0ZXJzIHRoYXQgbWF0Y2hlcyB3aXRoIGEgY29tYm8sIHNoZSBnZXRzIG9uZSBwb2ludCBmb3IgdGhlIGNvbWJvLiBDb21ib3MgbWF5IG92ZXJsYXAgd2l0aCBlYWNoIG90aGVyIG9yIGV2ZW4gZmluaXNoIGF0IHRoZSBzYW1lIHRpbWUhIEZvciBleGFtcGxlIGlmIE4gPSAzIGFuZCB0aGUgdGhyZWUgcG9zc2libGUgY29tYm9zIGFyZSAmcXVvdDtBQkEmcXVvdDssICZxdW90O0NCJnF1b3Q7LCBhbmQgJnF1b3Q7QUJBQ0ImcXVvdDssIGFuZCBCZXNzaWUgcHJlc3NlcyAmcXVvdDtBQkFDQiZxdW90Oywgc2hlIHdpbGwgZW5kIHdpdGggMyBwb2ludHMuIEJlc3NpZSBtYXkgc2NvcmUgcG9pbnRzIGZvciBhIHNpbmdsZSBjb21ibyBtb3JlIHRoYW4gb25jZS48XC9wPjxwPkJlc3NpZSBvZiBjb3Vyc2Ugd2FudHMgdG8gZWFybiBwb2ludHMgYXMgcXVpY2tseSBhcyBwb3NzaWJsZS4gSWYgc2hlIHByZXNzZXMgZXhhY3RseSBLIGJ1dHRvbnMgKDEgJmx0Oz0gSyAmbHQ7PSAxLDAwMCksIHdoYXQgaXMgdGhlIG1heGltdW0gbnVtYmVyIG9mIHBvaW50cyBzaGUgY2FuIGVhcm4/PFwvcD4iLCJpbnB1dCI6Ijx1bD48bGk+TGluZSAxOiBUd28gc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzOiBOIGFuZCBLLjxcL2xpPjxsaT5MaW5lcyAyLi5OKzE6IExpbmUgaSsxIGNvbnRhaW5zIG9ubHkgdGhlIHN0cmluZyBTX2ksIHJlcHJlc2VudGluZyBjb21ibyBpLjxcL2xpPjxcL3VsPiIsIm91dHB1dCI6Ijx1bD48bGk+TGluZSAxOiBBIHNpbmdsZSBpbnRlZ2VyLCB0aGUgbWF4aW11bSBudW1iZXIgb2YgcG9pbnRzIEJlc3NpZSBjYW4gb2J0YWluLjxcL2xpPjxcL3VsPiIsImhpbnQiOiI8aDQ+T3V0cHV0IERldGFpbHM8XC9oND48cD5UaGUgb3B0aW1hbCBzZXF1ZW5jZSBvZiBidXR0b25zIGluIHRoaXMgY2FzZSBpcyBBQkFDQkNCLCB3aGljaCBnaXZlcyA0IHBvaW50cy0tMSBmcm9tIEFCQSwgMSBmcm9tIEFCQUNCLCBhbmQgMiBmcm9tIENCLjxcL3A+Iiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=