시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 33 11 10 38.462%

문제

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

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

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

입력

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

출력

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

예제 입력

6 10
browndcodw
cow
milk
white
black
brown
farmer

예제 출력

2

힌트

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