소 타이핑 | cho.sh

문제

소들이 이메일을 발견하고 Farmer John에게서 오는 메시지를 즐겁게 받아 보고 있습니다. 하지만 발굽으로는 보통 키보드를 쓰기가 어려워 답장하기가 만만치 않습니다. 그래서 Farmer John은 소 전용 입력 장치를 만들었습니다.

이 장치에는 previous, next, add, print 네 개의 버튼과 화면이 있습니다. 소는 글자를 직접 입력하는 대신, 글자를 하나씩 골라 이어 붙여 단어를 만듭니다. 소들은 항상 대문자만 사용합니다.

소가 입력하는 모든 단어는 정해진 사전(입력으로 주어짐)에 들어 있는 단어입니다. 사전의 어떤 단어도 길이가 20을 넘지 않습니다.

화면에는 두 줄이 표시됩니다.

지금까지 만든 단어
다음에 올 수 있는 글자들의 목록 (그중 정확히 하나가 강조 표시됨)

next와 previous 버튼은 이 목록에서 강조 표시를 다음 글자나 이전 글자로 옮깁니다. 목록은 순환합니다. 마지막 글자에서 next를 누르면 첫 글자로, 첫 글자에서 previous를 누르면 마지막 글자로 이동합니다.

다음에 올 수 있는 글자 목록에는, 지금까지 입력한 내용에 이어 붙였을 때 여전히 사전의 어떤 단어로 이어질 수 있는 글자만 들어갑니다. 예를 들어 BD로 시작하는 사전 단어가 없다면, B를 입력한 뒤 목록에 D는 절대 나타나지 않습니다. 만든 단어가 비어 있을 때 목록에는 모든 사전 단어의 첫 글자가 들어갑니다.

강조된 글자를 추가하면 그 글자가 현재 단어의 끝에 붙고, 다음에 올 수 있는 글자 목록이 즉시 다시 계산됩니다. 그리고 강조 표시는 새 목록에서 알파벳순으로 가장 앞선 글자로 초기화됩니다.

예를 들어 사전이 ACE, APPLE, BANANA, PEAR라고 합시다. 목록은 처음에 A B P이고 A가 강조됩니다. 여기서 A를 추가하면 목록은 C P가 되고, (알파벳순으로 가장 앞선) C가 강조됩니다.

print를 누르면 완성된 단어가 이메일에 추가되고, 화면이 초기화되어 다음 단어를 위해 처음부터 다시 시작합니다.

위의 네 단어 사전으로 단어 APPLE을 입력하는 과정은 다음과 같습니다 (*A*는 A가 강조되었다는 뜻입니다).

동작         단어          가능한 글자
[처음]       _________     *A* B P
ADD          A________     *C* P
NEXT         A________     C *P*
ADD          AP_______     *P*
ADD          APP______     *L*
ADD          APPL_____     *E*
ADD          APPLE____
PRINT        _________     *A* B P

이렇게 APPLE을 입력하는 데에는 버튼을 7번 눌러야 합니다.

소는 항상 버튼을 최소한으로 누르므로, 강조 표시를 현재 위치에서 목표 글자로 옮기는 비용은 두 방향(next로 앞으로 가기, previous로 뒤로 가기) 중 더 짧은 순환 거리입니다.

사전과 짧은 이메일이 주어질 때, 이메일의 모든 단어를 입력하는 데 필요한 버튼 누름(이동, 추가, 인쇄)의 총횟수를 구하세요.

입력

첫째 줄: 정수 $D$ ($1 \le D < 25000$). 사전에 있는 단어의 개수입니다.
다음 $D$개의 줄: 한 줄에 사전 단어가 하나씩 주어집니다. 각 단어는 대문자 A–Z로 이루어지고 길이는 1 이상 20 이하이며, $D$개의 단어는 모두 서로 다릅니다.
그다음 줄: 정수 $N$ ($1 \le N \le 20$). 이메일에 들어 있는 단어의 개수입니다.
다음 $N$개의 줄: 한 줄에 입력할 단어가 하나씩 주어집니다. 각 단어는 반드시 사전에 존재합니다.

출력

이메일 전체를 입력하는 데 필요한 버튼 누름의 총횟수를 정수 하나로 출력하세요. 각 단어 뒤에 누르는 print 한 번도 포함합니다.