퀀텀

한 연구팀이 자기 디스크에 데이터를 저장하고 조작하는 새로운 방법을 개발하고 있다. 이 방법은 디스크의 섹터에 퀀텀 연산(quantum operation)을 적용한다. 각 퀀텀 연산은 일정한 양의 에너지를 소비하며, 저장 장치가 소비하는 에너지가 많을수록 장치는 더 뜨거워진다. 사용할 수 있는 퀀텀 연산들과 각각의 비용이 주어질 때, 주어진 이진 문자열을 원하는 이진 문자열로 바꾸는 데 드는 최소 총 비용을 계산하는 프로그램을 작성하라.

이진 문자열의 길이는 $1 \le L \le 20$이다. 모든 퀀텀 연산은 같은 길이 $L$의 문자열이며, 다음 네 글자로 이루어진다.

• N — 아무것도 하지 않는다(비트를 그대로 둔다).
• F — 비트를 반전시킨다.
• S — 비트를 1로 만든다.
• C — 비트를 0으로 만든다.

연산의 $i$번째 글자는 이진 문자열의 $i$번째 위치에 있는 비트에 작용한다. 연산을 한 번 적용하면 문자열의 모든 위치가 해당 글자에 따라 동시에 변환된다. 연산은 임의의 순서로, 원하는 횟수만큼 적용할 수 있다. 이진 문자열은 연산들의 나열을 차례로 적용하여 변환되며, 총 에너지 비용은 수행한 연산들의 비용의 합이다. 각 문자열 쌍에 대해 첫 번째 문자열을 두 번째 문자열로 바꾸는 최소 총 비용을 구하거나, 불가능함을 판정하라.

첫 번째 줄에 테스트 케이스의 수 $N$ ($1 \le N \le 20$)이 주어진다. 각 테스트 케이스는 다음과 같이 주어진다.

• 한 줄에 세 정수 $L$, $\mathit{nop}$, $\mathit{nw}$가 공백 하나로 구분되어 주어진다. $L$ ($1 \le L \le 20$)은 이진 문자열과 연산의 길이, $\mathit{nop}$ ($\mathit{nop} \le 32$)은 사용할 수 있는 퀀텀 연산의 수, $\mathit{nw}$ ($\mathit{nw} \le 20$)는 변환해야 할 이진 문자열의 수이다.
• 이어서 $\mathit{nop}$개의 줄이 주어지며, 각 줄에는 퀀텀 연산의 정의(N, F, S, C로 이루어진 길이 $L$의 문자열)와 에너지 비용 $c_i$ ($0 \le c_i \le 1000$)가 공백 하나로 구분되어 주어진다.
• 이어서 $\mathit{nw}$개의 줄이 주어지며, 각 줄에는 길이 $L$의 이진 문자열 두 개가 공백 하나로 구분되어 주어진다. 가능하다면 첫 번째 문자열을 사용할 수 있는 연산들로 두 번째 문자열로 바꾸어야 한다. 이진 문자열은 0과 1의 나열로 표기된다.

각 테스트 케이스마다, 각 이진 문자열을 변환하는 최소 에너지 비용을 입력과 같은 순서로 한 줄에 공백 하나로 구분하여 출력한다. 어떤 이진 문자열을 목표 문자열로 바꿀 수 없다면, 비용 대신 그 자리에 NP(not possible)를 출력한다.