D. Director of Orz Pandas
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Prof. Xie is a highly reputated scholar from SAST and the director of an important research program related to Orz Pandas. The Orz Pandas are telling a story of Prof. Xie to other pandas:

Once upon a time Prof. Xie wanted to buy a new house. He wanted the house to have $$$n$$$ features, and his spouse, Prof. Zhang wanted other $$$m$$$ features. Unfortunately, features wanted by Prof. Xie may conflict with features wanted by Prof. Zhang.

A panda wants to solve this situation mathematically. He assigns one weight $$$w_i$$$ for each feature $$$i$$$ and trys to choose some features with no conflicting pairs and maxmizing the sum of weights of choosen features.

Now you should tell him the maximized weight sum so he can check his solution.

Input

There are multiple test cases. Please process until EOF.

For each test case, the first line contains two integers $$$n$$$ and $$$m$$$.

The second line contains $$$n+m$$$ integers $$$w_1, \cdots, w_{n+m}$$$. $$$w_i$$$ is the weight of the $$$i$$$-th feature. The $$$1, 2, \cdots, n$$$-th features are wanted by Prof. Xie and the other features are wanted by Prof. Zhang.

The third line contains an integer $$$k$$$. Each of the next $$$k$$$ lines contains two integers $$$p_i$$$ and $$$q_i$$$, representing the $$$p_i$$$-th feature conflicts with the $$$q_i$$$-th feature.

It's guaranteed $$$1 \leq n, m \leq 100$$$, $$$1 \leq k \leq 10000$$$, $$$1 \leq w_i \leq 10^7$$$, $$$1 \leq p_i \leq n$$$, $$$n \lt q_i \leq n+m$$$.

Output

For each test case, output one line containing the answer.

Example
Input
2 2
4 3 8 2
3
1 3
1 4
2 4
Output
11