시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 30 23 16 84.211%

문제

슈퍼히어로 박승원은 결국 지구를 침략한 악당 로봇들을 해킹하는 데 성공했다. 로봇은 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+IDVcdWJjODhcdWM5ZjggXHViYjM4XHVjNzkwXHVhYzAwICZxdW90O0NCJnF1b3Q7LCBcdWM4MDRcdWNjYjRcdWFjMDAgJnF1b3Q7QUJBQ0ImcXVvdDtcdWM2NDAgXHViOWU0XHVjZTZkXHViNDE4XHVjNWI0XHVjMTFjIDNcdWJjODhcdWM3NTggXHVhY2Y1XHVhY2E5XHVjNzQ0IFx1YzEzMVx1YWNmNVx1ZDU1YyBcdWFjODNcdWFjZmMgXHVhYzE5XHViMmU0LiBcdWM3NzQgXHVjNjA4XHVjODFjXHVjNWQwXHVjMTFjIFx1YmNmY1x1YzIxOCBcdWM3ODhcdWIyZTRcdWMyZGNcdWQ1M2MgXHVjNWVjXHViN2VjXHVhYzFjXHVjNzU4IFx1Y2RlOFx1YzU3ZFx1YzgxMFx1Yzc0NCBcdWQ1NWNcdWFlYmNcdWJjODhcdWM1ZDAgXHVhY2Y1XHVhY2E5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1YjYxMFx1ZDU1YyBcdWQ1NWMgXHVjZGU4XHVjNTdkXHVjODEwXHVjNzQ0IFx1YzVlY1x1YjdlY1x1YmM4OCBcdWMwYWNcdWM2YTlcdWQ1NjAgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNmIwXHViOWFjXHVjNzU4IFx1YzI4OFx1ZDM3Y1x1ZDc4OFx1YzViNFx1Yjg1YyBcdWJjMTVcdWMyYjlcdWM2ZDBcdWM1ZDBcdWFjOGNcdWIyOTQgXHVjMmRjXHVhYzA0XHVjNzc0IFx1YzVjNlx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgXHVjODE1XHVkNjU1XHVkNzg4IEtcdWJjODhcdWJjMTZcdWM1ZDAgXHViYzg0XHVkMmJjXHVjNzQ0IFx1YjIwNFx1Yjk3YyBcdWMyMTggXHVjNWM2XHViMmU0LiAoMSAmbHQ7PSBLICZsdDs9IDEwMDApIFx1YzZiMFx1YjlhYyBcdWJhYThcdWI0NTAgXHViYzE1XHVjMmI5XHVjNmQwXHVjNzQ0IFx1YjNjNFx1YzY0MCBcdWFkZjhcdWFjMDAgXHVhY2Y1XHVhY2E5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjZDVjXHViMzAwIFx1ZDY5Zlx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NzRcdWM4ZmNcdWM3OTAuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cclxuXHRcdWNjYWJcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IE5cdWFjZmMgS1x1YWMxYyBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzAsIFx1Yzc3NFx1ZDZjNCBOXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBcdWNkZThcdWM1N2RcdWM4MTAgU2lcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LlxyXG48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cclxuXHRcdWJjMTVcdWMyYjlcdWM2ZDBcdWM3NzQgXHVhY2Y1XHVhY2E5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjZDVjXHViMzAwIFx1ZDY5Zlx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuXHJcbjxcL3A+XHJcbiIsImhpbnQiOiI8cD5cclxuXHRBQkFDQkNCIFx1Yjk3YyBcdWIyMGNcdWI3ZWMgXHVhY2Y1XHVhY2E5XHVkNTU4XHViYTc0IEFCQVx1YzY0MCBcdWQ1NWNcdWJjODgsIEFCQUNCXHVjNjQwIFx1ZDU1Y1x1YmM4OCwgQ0JcdWM2NDAgXHViNDUwXHViYzg4IFx1YjllNFx1Y2U2ZFx1YjQxOFx1YzViNCBcdWNkMWQgNFx1YmM4OCBcdWFjZjVcdWFjYTlcdWM1ZDAgXHVjMTMxXHVhY2Y1XHVkNTVjXHViMmU0LlxyXG48XC9wPiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNTkwNSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlZpZGVvIEdhbWUiLCJkZXNjcmlwdGlvbiI6IjxwPkJlc3NpZSBpcyBwbGF5aW5nIGEgdmlkZW8gZ2FtZSEgSW4gdGhlIGdhbWUsIHRoZSB0aHJlZSBsZXR0ZXJzICZhcG9zO0EmYXBvczssICZhcG9zO0ImYXBvczssIGFuZCAmYXBvcztDJmFwb3M7IGFyZSB0aGUgb25seSB2YWxpZCBidXR0b25zLiBCZXNzaWUgbWF5IHByZXNzIHRoZSBidXR0b25zIGluIGFueSBvcmRlciBzaGUgbGlrZXM7IGhvd2V2ZXIsIHRoZXJlIGFyZSBvbmx5IE4gZGlzdGluY3QgY29tYm9zIHBvc3NpYmxlICgxICZsdDs9IE4gJmx0Oz0gMjApLiBDb21ibyBpIGlzIHJlcHJlc2VudGVkIGFzIGEgc3RyaW5nIFNfaSB3aGljaCBoYXMgYSBsZW5ndGggYmV0d2VlbiAxIGFuZCAxNSBhbmQgY29udGFpbnMgb25seSB0aGUgbGV0dGVycyAmYXBvcztBJmFwb3M7LCAmYXBvcztCJmFwb3M7LCBhbmQgJmFwb3M7QyZhcG9zOy48XC9wPjxwPldoZW5ldmVyIEJlc3NpZSBwcmVzc2VzIGEgY29tYmluYXRpb24gb2YgbGV0dGVycyB0aGF0IG1hdGNoZXMgd2l0aCBhIGNvbWJvLCBzaGUgZ2V0cyBvbmUgcG9pbnQgZm9yIHRoZSBjb21iby4gQ29tYm9zIG1heSBvdmVybGFwIHdpdGggZWFjaCBvdGhlciBvciBldmVuIGZpbmlzaCBhdCB0aGUgc2FtZSB0aW1lISBGb3IgZXhhbXBsZSBpZiBOID0gMyBhbmQgdGhlIHRocmVlIHBvc3NpYmxlIGNvbWJvcyBhcmUgJnF1b3Q7QUJBJnF1b3Q7LCAmcXVvdDtDQiZxdW90OywgYW5kICZxdW90O0FCQUNCJnF1b3Q7LCBhbmQgQmVzc2llIHByZXNzZXMgJnF1b3Q7QUJBQ0ImcXVvdDssIHNoZSB3aWxsIGVuZCB3aXRoIDMgcG9pbnRzLiBCZXNzaWUgbWF5IHNjb3JlIHBvaW50cyBmb3IgYSBzaW5nbGUgY29tYm8gbW9yZSB0aGFuIG9uY2UuPFwvcD48cD5CZXNzaWUgb2YgY291cnNlIHdhbnRzIHRvIGVhcm4gcG9pbnRzIGFzIHF1aWNrbHkgYXMgcG9zc2libGUuIElmIHNoZSBwcmVzc2VzIGV4YWN0bHkgSyBidXR0b25zICgxICZsdDs9IEsgJmx0Oz0gMSwwMDApLCB3aGF0IGlzIHRoZSBtYXhpbXVtIG51bWJlciBvZiBwb2ludHMgc2hlIGNhbiBlYXJuPzxcL3A+IiwiaW5wdXQiOiI8dWw+PGxpPkxpbmUgMTogVHdvIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2VyczogTiBhbmQgSy48XC9saT48bGk+TGluZXMgMi4uTisxOiBMaW5lIGkrMSBjb250YWlucyBvbmx5IHRoZSBzdHJpbmcgU19pLCByZXByZXNlbnRpbmcgY29tYm8gaS48XC9saT48XC91bD4iLCJvdXRwdXQiOiI8dWw+PGxpPkxpbmUgMTogQSBzaW5nbGUgaW50ZWdlciwgdGhlIG1heGltdW0gbnVtYmVyIG9mIHBvaW50cyBCZXNzaWUgY2FuIG9idGFpbi48XC9saT48XC91bD4iLCJoaW50IjoiPGg0Pk91dHB1dCBEZXRhaWxzPFwvaDQ+PHA+VGhlIG9wdGltYWwgc2VxdWVuY2Ugb2YgYnV0dG9ucyBpbiB0aGlzIGNhc2UgaXMgQUJBQ0JDQiwgd2hpY2ggZ2l2ZXMgNCBwb2ludHMtLTEgZnJvbSBBQkEsIDEgZnJvbSBBQkFDQiwgYW5kIDIgZnJvbSBDQi48XC9wPiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d