As the end of the 2017/18 campaign approaches, football clubs across Europe will be assessing theirs quads 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^tℎ 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 d_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 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 ≤ n ≤ 1000), the number of players of Real Madrid.
The following n lines, each contains two integers ai(1 ≤ ai≤ 1000),bi(1 ≤ bi≤ 1000), the ability value
and the transfer value of the ith player of Real Madrid.
The next line contains an integer m(1 ≤ m ≤ 1000), the number of players in the sale.
The following m lines, each contains two integers ci(1 ≤ ci≤ 1000),di(1 ≤ di≤ 1000), the ability value and the transfer value of the itℎ player in the sale.
The next line contains an integer P(1 ≤ P ≤ 1000), the money Real Madrid has at the beginning.
It’s guaranteed that the sum of bi is no more than 1000.

输出描述:

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

2
2
92 77
22 22
2
87 29
46 50 
10 
1
1 1
5
92 77
22 23
87 29
46 50 
90 99
100

179
134