1091:DotA and LOL

时间限制: 6 S | 内存限制: 65536 KB
Accept: 0 | Submit: 0
[提交] [状态] [讨论版]
描述

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

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

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 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, k100000

0ai, bik

1cin

1dim

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

HINT

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.

dota1=1, lol1=2, dota2=1, lol2=1

|dota1-lol1|=1, |dota2-lol2|=0

So maxDiff = 1. Two students will study DotA.


来源
2017年第八届福建省大学生程序设计竞赛正式赛C