Contest of Rope Pulling

Rope Pulling, also known as Tug of War, is a classic game. Zhang3 organized a rope pulling contest between Class 1 and Class 2.

There are $n$ students in Class 1 and $m$ students in Class 2. The $i^\mathrm{th}$ student has strength $w_i$ and beauty-value $v_i$. Zhang3 needs to choose some students from both classes, and let those chosen from Class 1 compete against those chosen from Class 2. It is also allowed to choose no students from a class or to choose all of them.

To be a fair contest, the total strength of both teams must be equal. To make the contest more beautiful, Zhang3 wants to choose such a set of students, that the total beauty-value of all participants is maximized. Please help her determine the optimal total beauty-value.

The first line of the input gives the number of test cases, $T \; (1 \le T \le 30)$. $T$ test cases follow.

For each test case, the first line contains two integers $n, m \; (1 \le n, m \le 1000)$, representing the number of students in Class 1 and Class 2.

Then $(n + m)$ lines follow, describing the students. The $i^\mathrm{th}$ line contains two integers $w_i, v_i \; (1 \le w_i \le 1000, \; -10^9 \le v_i \le 10^9)$, representing the strength and the beauty-value of the $i^\mathrm{th}$ student. The first $n$ students come from Class 1, while the other $m$ students come from Class 2.

The sum of $(n + m)$ in all test cases doesn't exceed $10^4$.

For each test case, print a line with an integer, representing the optimal total beauty-value.

2
3 4
4 7
3 8
2 2
1 4
5 8
1 3
4 4
1 2
1000 -10000
200 3000
800 5000

30
0

2020 Multi-University Training Contest 4