시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 53 22 19 46.341%

문제

단어가 w개 실린 사전이 하나 주어진다. 사전에 실린 단어들은 모두 a에서 z까지의 알파벳 소문자들로만 이루어져 있고, 길이는 각각 25자 이하이다.

길이가 l인 문자열 S도 하나 주어진다. 이 문자열에서 몇 개의 문자를 제거하면, 나머지를 사전에 실린 단어들로 표현해 낼 수 있다. 표현해 낼 수 있다는 것이 무슨 뜻인지는, 입출력 예시를 통해 이해하면 된다.

여러분이 할 일은 이렇게 사전에 실린 단어들로 이 문자열을 표현해 내기 위해, 문자열에서 제거해야 하는 문자의 최소 개수가 몇 개인지 계산하는 것이다.

입력

첫째 줄에 w와 l이 주어진다. (1≤w≤600, 2≤l≤300) 두 번째 줄에는 문자열 S가 주어진다. 이어지는 w개의 줄에는 사전 내의 각 단어가 한 줄에 한 개씩 주어진다.

출력

첫 줄에, S에서 제거해야만 하는 최소한의 문자 개수를 출력한다.

예제 입력 1

6 10
browndcodw
cow
milk
white
black
brown
farmer

예제 출력 1

2

힌트

browndcodw에서 두 개의 d를 제거하면, brown과 cow 두 개의 단어로 표현할 수 있다.

W3sicHJvYmxlbV9pZCI6IjE4NTYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIyZThcdWM1YjQgXHVhYzhjXHVjNzg0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWIyZThcdWM1YjRcdWFjMDAgd1x1YWMxYyBcdWMyZTRcdWI5YjAgXHVjMGFjXHVjODA0XHVjNzc0IFx1ZDU1OFx1YjA5OCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YzBhY1x1YzgwNFx1YzVkMCBcdWMyZTRcdWI5YjAgXHViMmU4XHVjNWI0XHViNGU0XHVjNzQwIFx1YmFhOFx1YjQ1MCBhXHVjNWQwXHVjMTFjIHpcdWFlNGNcdWM5YzBcdWM3NTggXHVjNTRjXHVkMzBjXHViY2IzIFx1YzE4Y1x1YmIzOFx1Yzc5MFx1YjRlNFx1Yjg1Y1x1YjljYyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVhY2UwLCBcdWFlMzhcdWM3NzRcdWIyOTQgXHVhYzAxXHVhYzAxIDI1XHVjNzkwIFx1Yzc3NFx1ZDU1OFx1Yzc3NFx1YjJlNC48XC9wPjxwPlx1YWUzOFx1Yzc3NFx1YWMwMCBsXHVjNzc4IFx1YmIzOFx1Yzc5MFx1YzVmNCBTXHViM2M0IFx1ZDU1OFx1YjA5OCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM1ZDBcdWMxMWMgXHViYTg3IFx1YWMxY1x1Yzc1OCBcdWJiMzhcdWM3OTBcdWI5N2MgXHVjODFjXHVhYzcwXHVkNTU4XHViYTc0LCBcdWIwOThcdWJhMzhcdWM5YzBcdWI5N2MgXHVjMGFjXHVjODA0XHVjNWQwIFx1YzJlNFx1YjliMCBcdWIyZThcdWM1YjRcdWI0ZTRcdWI4NWMgXHVkNDVjXHVkNjA0XHVkNTc0IFx1YjBiYyBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWQ0NWNcdWQ2MDRcdWQ1NzQgXHViMGJjIFx1YzIxOCBcdWM3ODhcdWIyZTRcdWIyOTQgXHVhYzgzXHVjNzc0IFx1YmIzNFx1YzJhOCBcdWI3M2JcdWM3NzhcdWM5YzBcdWIyOTQsIFx1Yzc4NVx1Y2Q5Y1x1YjgyNSBcdWM2MDhcdWMyZGNcdWI5N2MgXHVkMWI1XHVkNTc0IFx1Yzc3NFx1ZDU3NFx1ZDU1OFx1YmE3NCBcdWI0MWNcdWIyZTQuPFwvcD48cD5cdWM1ZWNcdWI3ZWNcdWJkODRcdWM3NzQgXHVkNTYwIFx1Yzc3Y1x1Yzc0MCBcdWM3NzRcdWI4MDdcdWFjOGMgXHVjMGFjXHVjODA0XHVjNWQwIFx1YzJlNFx1YjliMCBcdWIyZThcdWM1YjRcdWI0ZTRcdWI4NWMgXHVjNzc0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0NCBcdWQ0NWNcdWQ2MDRcdWQ1NzQgXHViMGI0XHVhZTMwIFx1YzcwNFx1ZDU3NCwgXHViYjM4XHVjNzkwXHVjNWY0XHVjNWQwXHVjMTFjIFx1YzgxY1x1YWM3MFx1ZDU3NFx1YzU3YyBcdWQ1NThcdWIyOTQgXHViYjM4XHVjNzkwXHVjNzU4IFx1Y2Q1Y1x1YzE4YyBcdWFjMWNcdWMyMThcdWFjMDAgXHViYTg3IFx1YWMxY1x1Yzc3OFx1YzljMCBcdWFjYzRcdWMwYjBcdWQ1NThcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+IiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIHdcdWM2NDAgbFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxJmxlO3cmbGU7NjAwLCAyJmxlO2wmbGU7MzAwKSBcdWI0NTAgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWJiMzhcdWM3OTBcdWM1ZjQgU1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NFx1YzViNFx1YzljMFx1YjI5NCB3XHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMwYWNcdWM4MDQgXHViMGI0XHVjNzU4IFx1YWMwMSBcdWIyZThcdWM1YjRcdWFjMDAgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NWMgXHVhYzFjXHVjNTI5IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPiIsIm91dHB1dCI6IjxwPlx1Y2NhYiBcdWM5MDRcdWM1ZDAsIFNcdWM1ZDBcdWMxMWMgXHVjODFjXHVhYzcwXHVkNTc0XHVjNTdjXHViOWNjIFx1ZDU1OFx1YjI5NCBcdWNkNWNcdWMxOGNcdWQ1NWNcdWM3NTggXHViYjM4XHVjNzkwIFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD4iLCJoaW50IjoiPHA+YnJvd25kY29kd1x1YzVkMFx1YzExYyBcdWI0NTAgXHVhYzFjXHVjNzU4IGRcdWI5N2MgXHVjODFjXHVhYzcwXHVkNTU4XHViYTc0LCBicm93blx1YWNmYyBjb3cgXHViNDUwIFx1YWMxY1x1Yzc1OCBcdWIyZThcdWM1YjRcdWI4NWMgXHVkNDVjXHVkNjA0XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjE4NTYiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJUaGUgQ293IExleGljb24iLCJkZXNjcmlwdGlvbiI6IjxwPkZldyBrbm93IHRoYXQgdGhlIGNvd3MgaGF2ZSB0aGVpciBvd24gZGljdGlvbmFyeSB3aXRoIFcgKDEgJmx0Oz0gVyAmbHQ7PSA2MDApIHdvcmRzLCBlYWNoIGNvbnRhaW5pbmcgbm8gbW9yZSAyNSBvZiB0aGUgY2hhcmFjdGVycyAmIzM5O2EmIzM5Oy4uJiMzOTt6JiMzOTsuIFRoZWlyIGNvd211bmljYXRpb24gc3lzdGVtLCBiYXNlZCBvbiBtb29pbmcsIGlzIG5vdCB2ZXJ5IGFjY3VyYXRlOyBzb21ldGltZXMgdGhleSBoZWFyIHdvcmRzIHRoYXQgZG8gbm90IG1ha2UgYW55IHNlbnNlLiBGb3IgaW5zdGFuY2UsIEJlc3NpZSBvbmNlIHJlY2VpdmVkIGEgbWVzc2FnZSB0aGF0IHNhaWQgJnF1b3Q7YnJvd25kY29kdyZxdW90Oy4gQXMgaXQgdHVybnMgb3V0LCB0aGUgaW50ZW5kZWQgbWVzc2FnZSB3YXMgJnF1b3Q7YnJvd25jb3cmcXVvdDsgYW5kIHRoZSB0d28gbGV0dGVyICZxdW90O2QmcXVvdDtzIHdlcmUgbm9pc2UgZnJvbSBvdGhlciBwYXJ0cyBvZiB0aGUgYmFybnlhcmQuPFwvcD5cclxuXHJcbjxwPlRoZSBjb3dzIHdhbnQgeW91IHRvIGhlbHAgdGhlbSBkZWNpcGhlciBhIHJlY2VpdmVkIG1lc3NhZ2UgKGFsc28gY29udGFpbmluZyBvbmx5IGNoYXJhY3RlcnMgaW4gdGhlIHJhbmdlICYjMzk7YSYjMzk7Li4mIzM5O3omIzM5Oykgb2YgbGVuZ3RoIEwgKDIgJmx0Oz0gTCAmbHQ7PSAzMDApIGNoYXJhY3RlcnMgdGhhdCBpcyBhIGJpdCBnYXJibGVkLiBJbiBwYXJ0aWN1bGFyLCB0aGV5IGtub3cgdGhhdCB0aGUgbWVzc2FnZSBoYXMgc29tZSBleHRyYSBsZXR0ZXJzLCBhbmQgdGhleSB3YW50IHlvdSB0byBkZXRlcm1pbmUgdGhlIHNtYWxsZXN0IG51bWJlciBvZiBsZXR0ZXJzIHRoYXQgbXVzdCBiZSByZW1vdmVkIHRvIG1ha2UgdGhlIG1lc3NhZ2UgYSBzZXF1ZW5jZSBvZiB3b3JkcyBmcm9tIHRoZSBkaWN0aW9uYXJ5LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+KiBMaW5lIDE6IFR3byBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnMsIHJlc3BlY3RpdmVseTogVyBhbmQgTDxcL3A+XHJcblxyXG48cD4qIExpbmUgMjogTCBjaGFyYWN0ZXJzIChmb2xsb3dlZCBieSBhIG5ld2xpbmUsIG9mIGNvdXJzZSk6IHRoZSByZWNlaXZlZCBtZXNzYWdlPFwvcD5cclxuXHJcbjxwPiogTGluZXMgMy4uVysyOiBUaGUgY293cyYjMzk7IGRpY3Rpb25hcnksIG9uZSB3b3JkIHBlciBsaW5lPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+KiBMaW5lIDE6IGEgc2luZ2xlIGludGVnZXIgdGhhdCBpcyB0aGUgc21hbGxlc3QgbnVtYmVyIG9mIGNoYXJhY3RlcnMgdGhhdCBuZWVkIHRvIGJlIHJlbW92ZWQgdG8gbWFrZSB0aGUgbWVzc2FnZSBhIHNlcXVlbmNlIG9mIGRpY3Rpb25hcnkgd29yZHMuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d