애드혹 번역

어느 날 웹 서핑을 하다가, 한 번도 본 적 없는 언어로 쓰인 웹 페이지를 발견했다. 그 언어의 문자 체계는 모국어와 같았고, 문법과 단어도 거의 비슷해 보였다. 신이 나서 웹 페이지를 "해독"하기 시작했다. 가장 먼저 시도한 방법은 모국어 사전에서 비슷한 단어를 골라 각 단어의 뜻을 추측하는 것이었다. 두 단어(서로 다른 언어에 속해 있더라도)가 가까울수록 뜻도 더 비슷할 것이다.

두 단어의 유사도를 재는 척도로 편집 거리를 쓰기로 했다. 두 문자열 사이의 편집 거리는 한 문자열을 다른 문자열로 바꾸는 데 필요한 삽입, 삭제, 치환의 최소 횟수로 정의한다. 예를 들어 "point"와 "spoon"의 편집 거리는 3이다. "point"에서 't'를 삭제하고 'i'를 'o'로 치환한 뒤 맨 앞에 's'를 삽입하면 "spoon"이 된다.

웹 텍스트의 각 단어에 모국어 단어를 하나씩 대응시켜, 전체 대응의 편집 거리가 최소가 되도록 하고 싶다. 어떤 대응의 편집 거리는 텍스트의 각 단어와 그에 대응하는 모국어 단어 사이의 편집 거리를 모두 더한 값이다. 텍스트에 두 번 이상 나오는 단어는 나온 횟수만큼 더한다.

번역은 텍스트 전체에서 일관되어야 한다. 즉, 텍스트의 어떤 단어가 여러 번 나오더라도 서로 다른 사전 단어를 대응시킬 수 없다. 마찬가지로 텍스트의 서로 다른 단어가 모국어에서 같은 뜻을 가져서도 안 된다.

웹 페이지에 "qwerty asdf zxcv"가 쓰여 있고 사전에 "qwert", "asf", "tyui", "zxcvb", "ghjk"가 들어 있다고 하자. 이때 페이지의 단어들을 다음과 같이 대응시킬 수 있고, 이 번역의 편집 거리는 3이다. "qwerty"에는 "qwert", "asdf"에는 "asf", "zxcv"에는 "zxcvb".

웹 페이지 텍스트와 사전의 단어 집합이 주어질 때, 가능한 모든 번역 중 최소 편집 거리를 구하는 프로그램을 작성하라.

첫째 줄에 두 정수 N과 M이 주어진다.

다음 N개 줄은 발견한 웹 페이지의 텍스트를 나타낸다. 이 텍스트는 소문자 알파벳과 공백으로만 이루어져 있다. 그다음 M개 줄에 한 줄에 하나씩 단어가 주어지며, 사용할 사전을 이룬다. 모든 단어는 소문자 알파벳으로만 이루어져 있고, 길이가 20자를 넘지 않는다.

1 ≤ N ≤ 100, 1 ≤ M ≤ 400이 보장된다. 또한 사전에는 단어가 충분히 많아서, 사전의 단어 수가 번역할 텍스트에 있는 단어의 종류 수보다 적지 않음이 보장된다. 텍스트의 각 줄 길이는 1000을 넘지 않는다.

가능한 최소 편집 거리를 한 줄에 출력한다.