시간 제한메모리 제한제출정답맞은 사람정답 비율
2 초 128 MB122514551.724%

문제

단어가 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 두 개의 단어로 표현할 수 있다.

W3sicHJvYmxlbV9pZCI6IjE4NTYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIyZThcdWM1YjQgXHVhYzhjXHVjNzg0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWIyZThcdWM1YjRcdWFjMDAgd1x1YWMxYyBcdWMyZTRcdWI5YjAgXHVjMGFjXHVjODA0XHVjNzc0IFx1ZDU1OFx1YjA5OCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YzBhY1x1YzgwNFx1YzVkMCBcdWMyZTRcdWI5YjAgXHViMmU4XHVjNWI0XHViNGU0XHVjNzQwIFx1YmFhOFx1YjQ1MCBhXHVjNWQwXHVjMTFjIHpcdWFlNGNcdWM5YzBcdWM3NTggXHVjNTRjXHVkMzBjXHViY2IzIFx1YzE4Y1x1YmIzOFx1Yzc5MFx1YjRlNFx1Yjg1Y1x1YjljYyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVhY2UwLCBcdWFlMzhcdWM3NzRcdWIyOTQgXHVhYzAxXHVhYzAxIDI1XHVjNzkwIFx1Yzc3NFx1ZDU1OFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhZTM4XHVjNzc0XHVhYzAwIGxcdWM3NzggXHViYjM4XHVjNzkwXHVjNWY0IFNcdWIzYzQgXHVkNTU4XHViMDk4IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1YzVkMFx1YzExYyBcdWJhODcgXHVhYzFjXHVjNzU4IFx1YmIzOFx1Yzc5MFx1Yjk3YyBcdWM4MWNcdWFjNzBcdWQ1NThcdWJhNzQsIFx1YjA5OFx1YmEzOFx1YzljMFx1Yjk3YyBcdWMwYWNcdWM4MDRcdWM1ZDAgXHVjMmU0XHViOWIwIFx1YjJlOFx1YzViNFx1YjRlNFx1Yjg1YyBcdWQ0NWNcdWQ2MDRcdWQ1NzQgXHViMGJjIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1ZDQ1Y1x1ZDYwNFx1ZDU3NCBcdWIwYmMgXHVjMjE4IFx1Yzc4OFx1YjJlNFx1YjI5NCBcdWFjODNcdWM3NzQgXHViYjM0XHVjMmE4IFx1YjczYlx1Yzc3OFx1YzljMFx1YjI5NCwgXHVjNzg1XHVjZDljXHViODI1IFx1YzYwOFx1YzJkY1x1Yjk3YyBcdWQxYjVcdWQ1NzQgXHVjNzc0XHVkNTc0XHVkNTU4XHViYTc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNWVjXHViN2VjXHViZDg0XHVjNzc0IFx1ZDU2MCBcdWM3N2NcdWM3NDAgXHVjNzc0XHViODA3XHVhYzhjIFx1YzBhY1x1YzgwNFx1YzVkMCBcdWMyZTRcdWI5YjAgXHViMmU4XHVjNWI0XHViNGU0XHViODVjIFx1Yzc3NCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDQgXHVkNDVjXHVkNjA0XHVkNTc0IFx1YjBiNFx1YWUzMCBcdWM3MDRcdWQ1NzQsIFx1YmIzOFx1Yzc5MFx1YzVmNFx1YzVkMFx1YzExYyBcdWM4MWNcdWFjNzBcdWQ1NzRcdWM1N2MgXHVkNTU4XHViMjk0IFx1YmIzOFx1Yzc5MFx1Yzc1OCBcdWNkNWNcdWMxOGMgXHVhYzFjXHVjMjE4XHVhYzAwIFx1YmE4NyBcdWFjMWNcdWM3NzhcdWM5YzAgXHVhY2M0XHVjMGIwXHVkNTU4XHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgd1x1YzY0MCBsXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyB3ICZsZTsgNjAwLCAyICZsZTsgbCAmbGU7IDMwMCkgXHViNDUwIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViYjM4XHVjNzkwXHVjNWY0IFNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzRcdWM1YjRcdWM5YzBcdWIyOTQgd1x1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjMGFjXHVjODA0IFx1YjBiNFx1Yzc1OCBcdWFjMDEgXHViMmU4XHVjNWI0XHVhYzAwIFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVkNTVjIFx1YWMxY1x1YzUyOSBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiIFx1YzkwNFx1YzVkMCwgU1x1YzVkMFx1YzExYyBcdWM4MWNcdWFjNzBcdWQ1NzRcdWM1N2NcdWI5Y2MgXHVkNTU4XHViMjk0IFx1Y2Q1Y1x1YzE4Y1x1ZDU1Y1x1Yzc1OCBcdWJiMzhcdWM3OTAgXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+YnJvd25kY29kd1x1YzVkMFx1YzExYyBcdWI0NTAgXHVhYzFjXHVjNzU4IGRcdWI5N2MgXHVjODFjXHVhYzcwXHVkNTU4XHViYTc0LCBicm93blx1YWNmYyBjb3cgXHViNDUwIFx1YWMxY1x1Yzc1OCBcdWIyZThcdWM1YjRcdWI4NWMgXHVkNDVjXHVkNjA0XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIxODU2IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiVGhlIENvdyBMZXhpY29uIiwiZGVzY3JpcHRpb24iOiI8cD5GZXcga25vdyB0aGF0IHRoZSBjb3dzIGhhdmUgdGhlaXIgb3duIGRpY3Rpb25hcnkgd2l0aCBXICgxICZsdDs9IFcgJmx0Oz0gNjAwKSB3b3JkcywgZWFjaCBjb250YWluaW5nIG5vIG1vcmUgMjUgb2YgdGhlIGNoYXJhY3RlcnMgJiMzOTthJiMzOTsuLiYjMzk7eiYjMzk7LiBUaGVpciBjb3dtdW5pY2F0aW9uIHN5c3RlbSwgYmFzZWQgb24gbW9vaW5nLCBpcyBub3QgdmVyeSBhY2N1cmF0ZTsgc29tZXRpbWVzIHRoZXkgaGVhciB3b3JkcyB0aGF0IGRvIG5vdCBtYWtlIGFueSBzZW5zZS4gRm9yIGluc3RhbmNlLCBCZXNzaWUgb25jZSByZWNlaXZlZCBhIG1lc3NhZ2UgdGhhdCBzYWlkICZxdW90O2Jyb3duZGNvZHcmcXVvdDsuIEFzIGl0IHR1cm5zIG91dCwgdGhlIGludGVuZGVkIG1lc3NhZ2Ugd2FzICZxdW90O2Jyb3duY293JnF1b3Q7IGFuZCB0aGUgdHdvIGxldHRlciAmcXVvdDtkJnF1b3Q7cyB3ZXJlIG5vaXNlIGZyb20gb3RoZXIgcGFydHMgb2YgdGhlIGJhcm55YXJkLjxcL3A+XHJcblxyXG48cD5UaGUgY293cyB3YW50IHlvdSB0byBoZWxwIHRoZW0gZGVjaXBoZXIgYSByZWNlaXZlZCBtZXNzYWdlIChhbHNvIGNvbnRhaW5pbmcgb25seSBjaGFyYWN0ZXJzIGluIHRoZSByYW5nZSAmIzM5O2EmIzM5Oy4uJiMzOTt6JiMzOTspIG9mIGxlbmd0aCBMICgyICZsdDs9IEwgJmx0Oz0gMzAwKSBjaGFyYWN0ZXJzIHRoYXQgaXMgYSBiaXQgZ2FyYmxlZC4gSW4gcGFydGljdWxhciwgdGhleSBrbm93IHRoYXQgdGhlIG1lc3NhZ2UgaGFzIHNvbWUgZXh0cmEgbGV0dGVycywgYW5kIHRoZXkgd2FudCB5b3UgdG8gZGV0ZXJtaW5lIHRoZSBzbWFsbGVzdCBudW1iZXIgb2YgbGV0dGVycyB0aGF0IG11c3QgYmUgcmVtb3ZlZCB0byBtYWtlIHRoZSBtZXNzYWdlIGEgc2VxdWVuY2Ugb2Ygd29yZHMgZnJvbSB0aGUgZGljdGlvbmFyeS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPiogTGluZSAxOiBUd28gc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzLCByZXNwZWN0aXZlbHk6IFcgYW5kIEw8XC9wPlxyXG5cclxuPHA+KiBMaW5lIDI6IEwgY2hhcmFjdGVycyAoZm9sbG93ZWQgYnkgYSBuZXdsaW5lLCBvZiBjb3Vyc2UpOiB0aGUgcmVjZWl2ZWQgbWVzc2FnZTxcL3A+XHJcblxyXG48cD4qIExpbmVzIDMuLlcrMjogVGhlIGNvd3MmIzM5OyBkaWN0aW9uYXJ5LCBvbmUgd29yZCBwZXIgbGluZTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPiogTGluZSAxOiBhIHNpbmdsZSBpbnRlZ2VyIHRoYXQgaXMgdGhlIHNtYWxsZXN0IG51bWJlciBvZiBjaGFyYWN0ZXJzIHRoYXQgbmVlZCB0byBiZSByZW1vdmVkIHRvIG1ha2UgdGhlIG1lc3NhZ2UgYSBzZXF1ZW5jZSBvZiBkaWN0aW9uYXJ5IHdvcmRzLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

Olympiad > USA Computing Olympiad > 2006-2007 Season > USACO February 2007 Contest > Silver 1번