Kuroni the Private Tutor

Description:

Input:

The first line of input contains two integers ($$$1 \le n, m \le 10^{5}$$$), denoting the number of questions of the exam and the number of students respectively.

The next $$$n$$$ lines contain two integers each, with the $$$i$$$-th line containing $$$l_{i}$$$ and $$$r_{i}$$$ ($$$0 \le l_{i} \le r_{i} \le m$$$).

The next line contains a single integer $$$q$$$ ($$$0 \le q \le m$$$).

The next $$$q$$$ lines contain two integers each, denoting $$$p_{i}$$$ and $$$s_{i}$$$ ($$$1 \le p_{i} \le m$$$, $$$0 \le s_{i} \le n$$$). It is guaranteed that all $$$p_{i}$$$ are distinct and if $$$p_{i} \le p_{j}$$$, then $$$s_{i} \ge s_{j}$$$.

The last line contains a single integer $$$t$$$ ($$$0 \le t \le nm$$$), denoting the total score of all students.

Output:

Output two integers: the maximum number of students who could have gotten as many points as the student with rank $$$1$$$, and the maximum possible score for rank $$$1$$$ achieving this maximum number of students. If there is no valid arrangement that fits the given data, output $$$-1$$$ $$$-1$$$.

Sample Input:

5 4
2 4
2 3
1 1
0 1
0 0
1
4 1
7

Sample Output:

3 2

Sample Input:

5 6
0 6
0 6
2 5
6 6
4 6
1
3 3
30

Sample Output:

-1 -1

Note:

For the first sample, here is one possible arrangement that fits the data:

Students $$$1$$$ and $$$2$$$ both solved problems $$$1$$$ and $$$2$$$.

Student $$$3$$$ solved problems $$$2$$$ and $$$3$$$.

Student $$$4$$$ solved problem $$$4$$$.

The total score of all students is $$$T = 7$$$. Note that the scores of the students are $$$2$$$, $$$2$$$, $$$2$$$ and $$$1$$$ respectively, which satisfies the condition that the student at rank $$$4$$$ gets exactly $$$1$$$ point. Finally, $$$3$$$ students tied for first with a maximum score of $$$2$$$, and it can be proven that we cannot do better with any other arrangement.