You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 3.0 seconds
Memory limit: 256.0 MB

# Problem
As a professional private tutor, Kuroni has to gather statistics of an exam. Kuroni has appointed you to complete this important task. You must not disappoint him.

The exam consists of $$$n$$$ questions, and $$$m$$$ students have taken the exam. Each question was worth $$$1$$$ point. Question $$$i$$$ was solved by at least $$$l_i$$$ and at most $$$r_i$$$ students. Additionally, you know that the total score of all students is $$$t$$$.

Furthermore, you took a glance at the final ranklist of the quiz. The students were ranked from $$$1$$$ to $$$m$$$, where rank $$$1$$$ has the highest score and rank $$$m$$$ has the lowest score. Ties were broken arbitrarily.

You know that the student at rank $$$p_i$$$ had a score of $$$s_i$$$ for $$$1 \le i \le q$$$.

You wonder if there could have been a huge tie for first place. Help Kuroni determine 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.

## Input Format
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 Format
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$$$.

## Examples
```input
5 4
2 4
2 3
1 1
0 1
0 0
1
4 1
7
```
```output
3 2
```
-----
```input
5 6
0 6
0 6
2 5
6 6
4 6
1
3 3
30
```
```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.

Now solve the problem and return the code.