1390：DotA and LOL

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 c_i.

2.     The i-th student belongs to dormitory d_i.

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 a_i.

4.     The number of students that choose LOL in the i-th dormitory must be less than or equal to b_i

5.     Let the number of students that choose DotA and the number of students that choose LOL in class i be dota_i and lol_i, respectively. You should minimize maxDiff=max|dota_i-lol_i|.

6.     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 a_i, the (2i)-th integer is b_i.

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 c_i, and the (2i)-th integer is d_i.

n, m, k≤100000

0≤a_i, b_i≤k

1≤c_i≤n

1≤d_i≤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

Following students are in class 1: 1 2 3

Following students are in class 2: 4 5

Following students are in dormitory 1: 1 2

Following students are in dormitory 2: 3 4 5

Since there will be at most 0 students in dormitory 1 studying DotA. So student 1 and student 2 must learn LOL.

Student 3 and student 4 can study DotA, in the meantime, student 5 studies LOL.

dota₁=1, lol₁=2, dota₂=1, lol₂=1

|dota₁-lol₁|=1, |dota₂-lol₂|=0

So maxDiff = 1. Two students will study DotA.