주소 대응

연구자 우노(Uuno)는 학생들을 대상으로 설문을 진행하며 각자에게 이메일 주소를 적어 달라고 했다. 그런데 많은 학생이 적은 주소가 매우 알아보기 어려웠기 때문에, 우노는 확인을 위해 담임 선생님에게 전체 학생의 주소 목록을 따로 받았다. 이제 그는 다음 세 조건을 모두 만족하도록 두 목록을 서로 짝지으려 한다.

1. 첫 번째 목록의 각 주소는 두 번째 목록의 주소 정확히 하나에 대응된다.
2. 두 번째 목록의 어떤 주소도 첫 번째 목록의 둘 이상의 주소에 대응되지 않는다.
3. 조건 1과 2를 만족하는 모든 대응 중에서, 짝지어진 주소 쌍들의 차이 합이 최소이다.

두 주소의 차이는 다음과 같이 정의한다. 어떤 주소든 문자를 삽입, 삭제, 치환하는 연산을 통해 다른 주소로 바꿀 수 있다. 각 연산에는 정해진 비용이 있으며, 문자 하나를 삭제하는 비용은 $c_D$, 삽입하는 비용은 $c_A$, 어떤 문자를 다른 문자로 치환하는 비용은 아래 입력에서 주어진다. 두 주소의 차이는 두 번째 주소를 첫 번째 주소로 바꾸는 데 드는 최소 총비용으로 정의한다.

우노를 위해 위 세 조건을 만족하는 대응을 구하라. 최소 차이 합을 이루는 대응이 여러 개라면, 그중 사전순으로 가장 앞서는 대응을 출력한다.

• 첫째 줄: 정수 $N$ ($1 \le N \le 20$) — 학생에게 받은 주소의 개수.
• 둘째 줄: 학생에게 받은 $N$개의 이메일 주소가 공백으로 구분되어 주어진다.
• 셋째 줄: 정수 $M$ ($N \le M \le 20$) — 선생님에게 받은 주소의 개수.
• 넷째 줄: 선생님에게 받은 $M$개의 주소가 공백으로 구분되어 주어진다.
• 다섯째 줄: 두 정수 $c_D$와 $c_A$ ($0 \le c_D, c_A \le 10^6$) — 각각 문자 하나의 삭제 비용과 삽입 비용.
• 여섯째 줄: 주소에 쓰이는 서로 다른 문자의 개수 $K$ ($1 \le K \le 60$).
• 일곱째 줄: 정확히 $K$개의 문자가 구분자 없이 하나의 문자열로 주어진다.
• 이후 $K$개의 줄: 각 줄에 $K$개의 정수가 주어지는 $K \times K$ 행렬. $i$번째 줄 $j$번째 값 $c_{i,j}$ ($0 \le c_{i,j} \le 10^6$)는 일곱째 줄의 $i$번째 문자를 $j$번째 문자로 치환하는 비용이며, $c_{i,i} = 0$이다.

모든 주소는 최대 100개의 문자로 이루어지며, 주소에 등장하는 모든 문자는 일곱째 줄에 주어진 $K$개의 문자 중 하나이다.

• 첫째 줄: 모든 유효한 대응 중 최소 차이 합을 출력한다.
• 둘째 줄: $N$개의 정수 $v_1, \dots, v_N$을 공백으로 구분하여 출력한다. $v_i$는 $i$번째 학생 주소가 대응되는 선생님 목록에서의 위치(1부터 시작)이다. 최소 차이 합을 이루는 대응이 여러 개이면, 수열 $(v_1, v_2, \dots, v_N)$이 사전순으로 가장 작은 것을 출력한다.