안녕히, 그리고 물고기는 고마웠어요!

문제 정보

문제

문자 입력이 불편한 핸드폰이나 타블렛 같은 기계에서는 빠른 타이핑을 위해 강력한 자동 완성 기능을 제공합니다. 시리우스 사이버네틱스 주식회사에서 이번에 출시한 돌고래용 타블렛의 자동 완성 알고리즘은 사전에 저장된 N개의 단어들을 이용해 자동완성을 수행합니다. 돌고래가 새 단어를 타이핑하기 시작하면, 자동 완성 시스템은 지금까지 타이핑한 부분으로 시작하는 사전 내 단어 중 가장 출현 빈도가 높은 것을 자동으로 추천합니다. 만약 출현 빈도가 가장 높은 것이 여러 개 있다면 사전순으로(돌고래의 사전 역시 알파벳 순을 따릅니다) 가장 앞에 오는 단어가 추천되지요. 돌고래가 탭 키를 누르면 지금 추천된 단어가 자동으로 입력됩니다.

예를 들어 사전에 다음 7개의 단어가 들어 있다고 합시다.

단어 ALL AND FISH FOR SO THANKS THE
출현 빈도 4 3 8 6 4 9 9

이 때 문자열 "SO LONG AND THANKS FOR ALL THE FISH"를 타이핑한다고 하지요. 돌고래가 S를 누르면 자동완성 시스템은 자동으로 SO 를 추천하고, 여기서 탭 키를 누르면 SO가 입력됩니다. 이와 같은 방식으로 나머지 단어를 입력하는 데는 각 4번(LONG 은 사전에 없으므로 추천되지 않습니다), 3번(AN 과 탭), 2번 (T 와 탭), 3번(FO 와 탭), 2번 (A 와 탭), 3번(THE 모두 입력해야 합니다), 2번 (F 와 탭) 의 키 입력이 필요하지요. 여기에 7번의 공백 문자까지 입력하면 전체 28번 키를 눌러야 합니다.

단 이 타블렛에는 이미 입력한 단어를 편집하는 기능이 없기 때문에, THANKS를 입력하고 "S"를 지워서 "THANK"를 만들거나 "THE"를 입력하고 "RE"를 덧붙여서 "THERE"를 입력하는 것은 불가능합니다.

돌고래들의 지느러미는 타블렛의 입력에 적합하지 않으므로, 가능한 적은 타이핑 수로 모든 문장을 입력하고 싶습니다. 타블렛의 자동완성 알고리즘이 사용하는 단어들과 각 단어들의 출현 빈도가 주어질 때, 주어지는 긴 문자열을 입력하기 위해 필요한 최소 타이핑 수를 계산하는 프로그램을 작성하세요.

입력

입력의 첫 줄에는 테스트 케이스의 수 C(1 <= C <= 10)가 주어집니다. 각 테스트 케이스의 첫 줄에는 사전에 포함된 단어의 수 N (1 <= N <= 10000)과 입력할 단어의 수 M (1 <= M <= 20000)이 주어집니다. 그 후 N 줄에는 한 줄에 하나의 문자열과 정수로 사전에 포함된 단어와 해당 단어의 출현 빈도가 사전 순서와 무관하게 주어집니다. 같은 단어가 두번 이상 주어지는 일은 없으며, 출현 빈도는 1 과 10만 사이의 정수입니다. 그 다음 줄에 M개의 단어로 입력할 문자열이 주어집니다. 모든 단어는 알파벳 대문자이며, 길이는 최대 10입니다.

입력의 양이 많으므로 가능한 빠른 입력 함수를 이용하는 것이 좋습니다.

출력

각 테스트 케이스마다 한 줄에 모든 단어들을 입력하기 위해 필요한 최소 타자 수를 출력합니다

예제 입력

2
7 8
ALL 4
AND 3
FISH 8
FOR 6
SO 4
THANKS 9
THE 9
SO LONG AND THANKS FOR ALL THE FISH
7 8
ALL 4
AND 5
FISH 3
FOR 6
SO 8
THANKS 1
THE 2
SO LONG AND THANKS FOR ALL THE FISH

예제 출력

28
29

노트

19개의 댓글이 있습니다.