DotA and LOL are two computer games. University of Electronic Games(UEG) has set up two courses: DotA and LOL. The headmaster wants you to help students to choose their courses.
You are told:
1. The i-th student belongs to class ci.
2. The i-th student belongs to dormitory di.
There are some rules that must be followed:
1. Every student must choose at least one course from DotA and LOL.
2. Every student must choose at most one course from DotA and LOL.
3. The number of students that choose DotA in the i-th dormitory must be less than or equal to ai.
4. The number of students that choose LOL in the i-th dormitory must be less than or equal to bi
Let the number of students that choose DotA and the number of students that choose LOL in class i be dota-i andlol-i, respectively. You should minimize maxdiff = max|dota(i)-lol(i)|
5. While maxDiff is minimized, please minimize the number of students that’s playing DotA.
Just tell the headmaster the value of maxDiff and the minimum number of students learning DotA while maxDiff is minimized.
First line will contain one integer T (1 ≤ T ≤ 10): the number of testcases.
For each testcase:
There will be one integer n (the number of classes) in the first line.
One integer m (the number of dormitories) in the next line.
2m integers separated by one space in the next line. The (2i-1)-th integer is ai, the (2i)-th integer is bi.
One integer k (the number of students) in the next line.
2k integers separated by one space in the next line. The (2i-1)-th integer is ci, and the (2i)-th integer is di.
n,m,k<=100000
0<=ai,bi<=k
1<=ci<=n
1<=di<=m
It is guaranteed that at least one optimal solution exists.
For each testcase:
Output two integers in a line: maxDiff and the minimum number of students learning DotA while maxDiff is minimized.
1 2 2 0 2 2 1 5 1 1 1 1 1 2 2 2 2 2
1 2