3052: Transfer Window

As the end of the $2017/18$ campaign approaches, football clubs across Europe will be assessing their squads and deciding which areas they need to improve when the summer transfer window opens. Clubs could sell and buy players as they want.

$Aguin$ is a fan of Real Madrid, and he pays close attention to the summer transfer window. Among the data he collected, Real Madrid only has $P$ dollars for the transfer window with the financial pressure. Real Madrid has $n$ players, each of them has the ability value $a_{i}$ and the transfer value $b_{i}$. (Real Madrid can obtain $b_{i}$ dollars by selling the $i^{th}$ player).

Also there are $m$ players of other clubs are in the sale, each of them has the ability value $c_{i}$ and the transfer value $d_{i}$. (Real Madrid will cost $b_{i}$ dollars by buying the $i^{th}$ player)

$Aguin$ is curious the maximum sum of players' ability value Real Madrid could has. But he's too stupid to calculate it. Can you tell him?

Pay attention, what $Aguin$ want is the maximum sum, even the number of Real Madrid's players is less than 11.

The first line contains an integer number $T$, the number of test cases.

For each test case :
The first line contains an integer $n(1 \leq n \leq 1000)$, the number of players of Real Madrid.

The following $n$ lines, each contains two integers $a_{i}(1 \leq a_{i} \leq 1000), b_{i}(1 \leq b_{i} \leq 1000)$, the ability value and the transfer value of the $i^{th}$ player of Real Madrid.

The next line contains an integer $m(1 \leq m \leq 1000)$, the number of players in the sale.

The following $m$ lines, each contains two integers $c_{i}(1 \leq c_{i} \leq 1000), d_{i}(1 \leq d_{i} \leq 1000)$, the ability value and the transfer value of the $i^{th}$ player in the sale.

The next line contains an integer $P(1 \leq P \leq 1000)$, the money Real Madrid has at the beginning.

It’s guaranteed that the sum of $b_{i}$ is no more than $1000$.

For each test case print the minimum sum of players' ability value Real Madrid could has.

1
2
92 77
22 22
2
87 29
46 50
10

179