Kuroni the Private Tutor
Contest: Ozon Tech Challenge 2020 (Div.1 + Div.2, Rated, T-shirts + prizes!)
Difficulty rating: 3500
Tags: binary search, greedy

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

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

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.

Example input:
5 4
2 4
2 3
1 1
0 1
0 0
1
4 1
7

Example output:
3 2

Example input:
5 6
0 6
0 6
2 5
6 6
4 6
1
3 3
30

Example output:
-1 -1

Editorial:
Suppose we fix the scores of the students $$$b_0 \le b_1 \le … \le b_{m-1}$$$. We model our problem as a flow graph. Consider a flow graph where the left side contains the source and $$$n$$$ nodes denoting the problems, and the right side contains the sink and $$$m$$$ nodes denoting the students. Each problem node is connected to each student node with capacity $$$1$$$. The source is connected to the node for problem $$$i$$$ with minimum capacity $$$L_{i}$$$ and maximum capacity $$$R_{i}$$$. The node for student $$$i$$$ is connected to the sink with capacity $$$b_i$$$. Our assignment is valid iff there is a valid saturating flow.
We can build a flow graph with demands (minimum capacity for some edges) as a normal flow graph. You can find more information on how to build it here: https://cp-algorithms.com/graph/flow_with_demands.html. We want to ensure that our minimum cut is at least $$$T$$$. Let $$$B[i] = \displaystyle\sum_{i=0}^{i}b_i$$$ (with $$$B[-1]=0$$$), $$$L[i]$$$ and $$$R[i]$$$ denote the sum of the $$$i$$$ smallest $$$L$$$ and $$$R$$$ values respectively. Let $$$s_L$$$ denote the sum of all $$$L$$$ values.
Analyzing the possibilities for minimum cut, we can show that our minimum cut is at least $$$T$$$ iff the following two conditions hold for all $$$0 \le i \le m$$$ and $$$0 \le j \le n$$$:
$$$R[j] + B[i-1] + (n-j)(m-i) \ge T$$$
$$$L[j] + B[i-1] + (n-j)(m-i) \ge s_L$$$
If we fix the values of $$$b_i$$$, we can check whether these conditions hold using Convex Hull Trick in $$$O(n+m)$$$ (by fixing $$$i$$$ and varying $$$j$$$).
How to determine which $$$b_i$$$ values to use. From our formulas, it is clear that if there are no additional restrictions, if two sequences $$$a_i$$$, $$$b_i$$$ are such that $$$b_i$$$ majorizes $$$a_i$$$, then $$$b_i$$$ is a better choice than $$$a_i$$$.
We can binary search the maximum number of students with a tie for first place. We try to assign the minimum possible score for each student satisfying all the constraints given. We still have some additional "score" left before our sum of scores reach $$$T$$$. We want to determine the maximum score our highest-scoring student can obtain. It can be proven that the set of valid maximum scores forms a range starting from the smallest $$$x$$$ such that there exists a valid $$$b_i$$$ arrangement satisfying all the problem conditions except the conditions for flow. Thus, we can binary search to find $$$x$$$ and also binary search to find the maximum possible score.
The solution works in $$$O((n+m)\log^{2}n)$$$ time.