Investments

Investing is serious business! Mr. Jozef, a businessman in the farming and livestock sector (also known from the Zalew problem), knows this very well, and he has just started planning his budget for the upcoming year 2011.

Mr. Jozef has prepared a list of investments he could carry out on his farm (for example: building a wind power plant, a new barn, creating a website, or introducing ecological fertilizers), together with the cost of each one.

Of course, the goal of investing is to earn high profits. Mr. Jozef knows that certain combinations of investments will bring him very specific benefits. For example:

• Introducing ecological fertilizers and building a wind power plant (both must be done together!) will earn Mr. Jozef the award for the most ecological farmer of the year.
• Building a wind power plant will save a specific amount on the electricity bills.

(as the example above shows, a single investment can contribute to several different benefits at the same time)

Given the cost of each investment, the revenue that each achieved benefit brings, and which investments are required to achieve each benefit, compute the maximum profit (the sum of revenues from the achieved benefits minus the sum of costs of the investments carried out) that Mr. Jozef can achieve in 2011.

The list of achievable benefits may include some that require no investments at all.

The first line contains a single natural number $Z$ ($1 \le Z \le 10$), the number of test sets. The sets are then described one after another.

The first line of a set contains two natural numbers $A$ and $B$ ($1 \le A, B \le 100$). $A$ is the number of investments and $B$ is the number of possible benefits.

The second line of the set contains $A$ natural numbers $a_i$ ($1 \le a_i \le 1000000$), where $a_i$ is the cost of carrying out the $i$-th investment (investments are numbered from $1$ to $A$).

The third line contains $B$ natural numbers $b_i$ ($1 \le b_i \le 1000000$), where $b_i$ is the revenue from the $i$-th benefit (benefits are numbered from $1$ to $B$).

The fourth line contains a natural number $K$ ($1 \le K \le A \cdot B$).

Each of the next $K$ lines contains two natural numbers $x_i$ and $y_i$ separated by a space ($1 \le x_i \le A$, $1 \le y_i \le B$). This means that achieving the $y_i$-th benefit requires carrying out the $x_i$-th investment.

No pair $(x_i, y_i)$ appears in the input more than once.

For each test set, print the maximum achievable profit on its own line.