시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 38 30 21 84.000%

문제

슈퍼히어로 박승원은 결국 지구를 침략한 악당 로봇들을 해킹하는 데 성공했다. 로봇은 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+XHVjNmIwXHViOWFjXHVjNzU4IFx1YzI4OFx1ZDM3Y1x1ZDc4OFx1YzViNFx1Yjg1YyBcdWJjMTVcdWMyYjlcdWM2ZDBcdWM1ZDBcdWFjOGNcdWIyOTQgXHVjMmRjXHVhYzA0XHVjNzc0IFx1YzVjNlx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgXHVjODE1XHVkNjU1XHVkNzg4IEtcdWJjODhcdWJjMTZcdWM1ZDAgXHViYzg0XHVkMmJjXHVjNzQ0IFx1YjIwNFx1Yjk3YyBcdWMyMTggXHVjNWM2XHViMmU0LiAoMSAmbHQ7PSBLICZsdDs9IDEwMDApIFx1YzZiMFx1YjlhYyBcdWJhYThcdWI0NTAgXHViYzE1XHVjMmI5XHVjNmQwXHVjNzQ0IFx1YjNjNFx1YzY0MCBcdWFkZjhcdWFjMDAgXHVhY2Y1XHVhY2E5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjZDVjXHViMzAwIFx1ZDY5Zlx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NzRcdWM4ZmNcdWM3OTAuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cclxuXHRcdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBOXHVhY2ZjIEtcdWFjMWMgXHVjOGZjXHVjNWI0XHVjOWMwXHViYTcwLCBcdWM3NzRcdWQ2YzQgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVjZGU4XHVjNTdkXHVjODEwIFNpXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC5cclxuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHJcblx0XHViYzE1XHVjMmI5XHVjNmQwXHVjNzc0IFx1YWNmNVx1YWNhOVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1Y2Q1Y1x1YjMwMCBcdWQ2OWZcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LlxyXG48XC9wPlxyXG4iLCJoaW50IjoiPHA+XHJcblx0QUJBQ0JDQiBcdWI5N2MgXHViMjBjXHViN2VjIFx1YWNmNVx1YWNhOVx1ZDU1OFx1YmE3NCBBQkFcdWM2NDAgXHVkNTVjXHViYzg4LCBBQkFDQlx1YzY0MCBcdWQ1NWNcdWJjODgsIENCXHVjNjQwIFx1YjQ1MFx1YmM4OCBcdWI5ZTRcdWNlNmRcdWI0MThcdWM1YjQgXHVjZDFkIDRcdWJjODggXHVhY2Y1XHVhY2E5XHVjNWQwIFx1YzEzMVx1YWNmNVx1ZDU1Y1x1YjJlNC5cclxuPFwvcD4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjU5MDUiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJWaWRlbyBHYW1lIiwiZGVzY3JpcHRpb24iOiI8cD5CZXNzaWUgaXMgcGxheWluZyBhIHZpZGVvIGdhbWUhIEluIHRoZSBnYW1lLCB0aGUgdGhyZWUgbGV0dGVycyAmYXBvcztBJmFwb3M7LCAmYXBvcztCJmFwb3M7LCBhbmQgJmFwb3M7QyZhcG9zOyBhcmUgdGhlIG9ubHkgdmFsaWQgYnV0dG9ucy4gQmVzc2llIG1heSBwcmVzcyB0aGUgYnV0dG9ucyBpbiBhbnkgb3JkZXIgc2hlIGxpa2VzOyBob3dldmVyLCB0aGVyZSBhcmUgb25seSBOIGRpc3RpbmN0IGNvbWJvcyBwb3NzaWJsZSAoMSAmbHQ7PSBOICZsdDs9IDIwKS4gQ29tYm8gaSBpcyByZXByZXNlbnRlZCBhcyBhIHN0cmluZyBTX2kgd2hpY2ggaGFzIGEgbGVuZ3RoIGJldHdlZW4gMSBhbmQgMTUgYW5kIGNvbnRhaW5zIG9ubHkgdGhlIGxldHRlcnMgJmFwb3M7QSZhcG9zOywgJmFwb3M7QiZhcG9zOywgYW5kICZhcG9zO0MmYXBvczsuPFwvcD48cD5XaGVuZXZlciBCZXNzaWUgcHJlc3NlcyBhIGNvbWJpbmF0aW9uIG9mIGxldHRlcnMgdGhhdCBtYXRjaGVzIHdpdGggYSBjb21ibywgc2hlIGdldHMgb25lIHBvaW50IGZvciB0aGUgY29tYm8uIENvbWJvcyBtYXkgb3ZlcmxhcCB3aXRoIGVhY2ggb3RoZXIgb3IgZXZlbiBmaW5pc2ggYXQgdGhlIHNhbWUgdGltZSEgRm9yIGV4YW1wbGUgaWYgTiA9IDMgYW5kIHRoZSB0aHJlZSBwb3NzaWJsZSBjb21ib3MgYXJlICZxdW90O0FCQSZxdW90OywgJnF1b3Q7Q0ImcXVvdDssIGFuZCAmcXVvdDtBQkFDQiZxdW90OywgYW5kIEJlc3NpZSBwcmVzc2VzICZxdW90O0FCQUNCJnF1b3Q7LCBzaGUgd2lsbCBlbmQgd2l0aCAzIHBvaW50cy4gQmVzc2llIG1heSBzY29yZSBwb2ludHMgZm9yIGEgc2luZ2xlIGNvbWJvIG1vcmUgdGhhbiBvbmNlLjxcL3A+PHA+QmVzc2llIG9mIGNvdXJzZSB3YW50cyB0byBlYXJuIHBvaW50cyBhcyBxdWlja2x5IGFzIHBvc3NpYmxlLiBJZiBzaGUgcHJlc3NlcyBleGFjdGx5IEsgYnV0dG9ucyAoMSAmbHQ7PSBLICZsdDs9IDEsMDAwKSwgd2hhdCBpcyB0aGUgbWF4aW11bSBudW1iZXIgb2YgcG9pbnRzIHNoZSBjYW4gZWFybj88XC9wPiIsImlucHV0IjoiPHVsPjxsaT5MaW5lIDE6IFR3byBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnM6IE4gYW5kIEsuPFwvbGk+PGxpPkxpbmVzIDIuLk4rMTogTGluZSBpKzEgY29udGFpbnMgb25seSB0aGUgc3RyaW5nIFNfaSwgcmVwcmVzZW50aW5nIGNvbWJvIGkuPFwvbGk+PFwvdWw+Iiwib3V0cHV0IjoiPHVsPjxsaT5MaW5lIDE6IEEgc2luZ2xlIGludGVnZXIsIHRoZSBtYXhpbXVtIG51bWJlciBvZiBwb2ludHMgQmVzc2llIGNhbiBvYnRhaW4uPFwvbGk+PFwvdWw+IiwiaGludCI6IjxoND5PdXRwdXQgRGV0YWlsczxcL2g0PjxwPlRoZSBvcHRpbWFsIHNlcXVlbmNlIG9mIGJ1dHRvbnMgaW4gdGhpcyBjYXNlIGlzIEFCQUNCQ0IsIHdoaWNoIGdpdmVzIDQgcG9pbnRzLS0xIGZyb20gQUJBLCAxIGZyb20gQUJBQ0IsIGFuZCAyIGZyb20gQ0IuPFwvcD4iLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==