투자

투자는 진지한 일입니다! 농업과 축산업에 종사하는 사업가 유제프 씨(Zalew 문제로도 알려진 인물)는 이 사실을 잘 알고 있으며, 다가오는 2011년 예산 계획을 막 세우기 시작했습니다.

유제프 씨는 자신의 농장에서 진행할 수 있는 투자 목록(예: 풍력 발전소 건설, 새 축사 건설, 웹사이트 제작, 친환경 비료 도입)과 각 투자의 비용을 정리했습니다.

물론 투자의 목적은 높은 수익을 얻는 것입니다. 유제프 씨는 특정 투자 조합이 매우 구체적인 이익을 가져다준다는 것을 알고 있습니다. 예를 들면:

• 친환경 비료 도입과 풍력 발전소 건설을 (반드시 둘 다 동시에!) 진행하면, 유제프 씨는 올해의 가장 친환경적인 농부 상을 받게 됩니다.
• 풍력 발전소를 건설하면 전기 요금에서 일정 금액을 절약할 수 있습니다.

(위 예시에서 볼 수 있듯이, 하나의 투자는 동시에 여러 이익에 기여할 수 있습니다.)

각 투자의 비용, 달성한 각 이익이 가져오는 수입, 그리고 각 이익을 달성하기 위해 필요한 투자를 알고 있을 때, 유제프 씨가 2011년에 얻을 수 있는 최대 수익(달성한 이익의 수입 합계에서 진행한 투자의 비용 합계를 뺀 값)을 구하세요.

달성 가능한 이익 목록에는 어떤 투자도 필요하지 않은 이익이 포함될 수 있습니다.

첫 번째 줄에는 테스트 세트의 개수를 나타내는 자연수 $Z$ ($1 \le Z \le 10$)가 주어집니다. 이어서 각 세트가 차례로 주어집니다.

각 세트의 첫 번째 줄에는 두 자연수 $A$와 $B$ ($1 \le A, B \le 100$)가 주어집니다. $A$는 투자의 개수, $B$는 가능한 이익의 개수입니다.

두 번째 줄에는 $A$개의 자연수 $a_i$ ($1 \le a_i \le 1000000$)가 주어지며, $a_i$는 $i$번째 투자를 진행하는 비용입니다(투자는 $1$부터 $A$까지 번호를 매깁니다).

세 번째 줄에는 $B$개의 자연수 $b_i$ ($1 \le b_i \le 1000000$)가 주어지며, $b_i$는 $i$번째 이익의 수입입니다(이익은 $1$부터 $B$까지 번호를 매깁니다).

네 번째 줄에는 자연수 $K$ ($1 \le K \le A \cdot B$)가 주어집니다.

이어지는 $K$개의 줄에는 공백으로 구분된 두 자연수 $x_i$, $y_i$ ($1 \le x_i \le A$, $1 \le y_i \le B$)가 주어집니다. 이는 $y_i$번째 이익을 달성하려면 $x_i$번째 투자를 반드시 진행해야 함을 의미합니다.

같은 쌍 $(x_i, y_i)$는 입력에 두 번 이상 나타나지 않습니다.

각 테스트 세트마다 달성 가능한 최대 수익을 한 줄에 하나씩 출력하세요.