게으른 전신
시간 제한1초메모리 제한128 MB
각 사전 단어를 보낼 때, 같은 길이의 사전 단어들 중 해밍 거리로 유일하게 가장 가까운 문자열이 되도록 하면서 전송 시간(점 1초, 대시 2초)을 최소화하여 전체 합을 구합니다.
문제
Mirko는 다락방에서 전신기를 발견해 친구 Slavko에게 메시지를 보내려 한다. 전신기는 점(.)과 선(-)으로 이루어진 문자열을 보낸다. 점 하나를 보내려면 키를 1초 동안, 선 하나를 보내려면 2초 동안 눌러야 한다.
Mirko는 매우 게으르기 때문에 각 단어를 보낼 때 몇몇 기호를 바꾸어 전송 시간이 가능한 한 짧아지게 하려 한다.
Mirko와 Slavko는 모스 부호를 모르기 때문에, 앞으로 필요할 수 있는 모든 단어를 담은 사전을 함께 만들었다. Mirko가 어떤 원래 단어를 보낼 때는, Slavko가 다음 방식으로 그 원래 단어를 유일하게 알아낼 수 있어야 한다.
Slavko는 사전에서 원래 단어와 길이가 같은 단어들만 살펴본다. 그중 보낸 문자열과 다른 기호의 수가 가장 적은 단어를 고른다. 이때 최소 차이를 가지는 단어가 정확히 하나여야 하며, 그 단어가 원래 단어여야 한다.
사전과 Mirko가 보내려는 글이 주어진다. 단어 사이의 공백은 보낼 필요가 없을 때, 모든 단어를 유일하게 복원할 수 있도록 보내는 데 필요한 최소 총 시간을 구하시오.
입력
첫째 줄에 사전에 있는 단어의 수 N이 주어진다. (1 <= N <= 2000)
다음 N개의 줄에는 사전의 단어가 하나씩 주어진다. 각 단어는 길이가 12 이하이며, .와 -로만 이루어진 문자열이다.
그다음 줄에 Mirko가 보내려는 단어의 수 L이 주어진다. (1 <= L <= 10000)
다음 L개의 줄에는 Mirko가 보내려는 단어가 하나씩 주어진다. 이 단어들은 모두 사전에 있다.
출력
Slavko가 모든 단어를 유일하게 복원할 수 있도록 메시지를 보내는 데 필요한 최소 시간을 출력한다.
힌트
첫 번째 공개 테스트에서 첫 단어 대신 ....를 보내면 4초가 걸리고, 두 번째 단어 대신 -..-를 보내면 6초가 더 걸린다. 따라서 총 10초가 필요하다.