CF1305H.Kuroni the Private Tutor

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.

作为一名专业的私人辅导老师，库罗尼需要汇总一次考试的统计数据。库罗尼已委派你完成这项重要任务，你绝不能让他失望。

本次考试共有 $n$ 道题目，$m$ 名学生参加了考试。每道题目的分值均为 $1$ 分。第 $i$ 题至少被 $l_i$ 名学生、至多被 $r_i$ 名学生答对。此外，你还知道所有学生的总得分之和为 $t$。

另外，你匆匆浏览了本次测验的最终排名表。学生按得分从高到低排序，依次编号为 $1$ 至 $m$，其中排名 $1$ 的学生得分最高，排名 $m$ 的学生得分最低；若出现并列，则任意打破平局。

你已知：对于 $1 \le i \le q$，排名为 $p_i$ 的学生得分为 $s_i$。

你不禁好奇：是否可能有大量学生并列第一？请帮助库罗尼确定：最多可能有多少名学生与排名第 $1$ 的学生得分相同，以及在达到该最多人数的前提下，排名第 $1$ 的学生所能取得的最高得分是多少。

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.

输入的第一行包含两个整数（$1 \le n, m \le 10^{5}$），分别表示考试的题目数量和学生人数。

接下来的 $n$ 行每行包含两个整数，其中第 $i$ 行包含 $l_{i}$ 和 $r_{i}$（$0 \le l_{i} \le r_{i} \le m$）。

下一行包含一个整数 $q$（$0 \le q \le m$）。

接下来的 $q$ 行每行包含两个整数，表示 $p_{i}$ 和 $s_{i}$（$1 \le p_{i} \le m$，$0 \le s_{i} \le n$）。保证所有 $p_{i}$ 互不相同，且若 $p_{i} \le p_{j}$，则有 $s_{i} \ge s_{j}$。

最后一行包含一个整数 $t$（$0 \le t \le nm$），表示所有学生的总分。

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

输出两个整数：可能获得与排名第 $1$ 的学生相同分数的学生的最大人数，以及在达到该最大人数的前提下，排名第 $1$ 的学生所能取得的最高分数。如果不存在符合给定数据的有效安排，则输出 $-1$ $-1$。

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.

对于第一个样例，以下是一种符合数据的可能安排：

学生 $1$ 和 $2$ 均解出了题目 $1$ 和 $2$。

学生 $3$ 解出了题目 $2$ 和 $3$。

学生 $4$ 解出了题目 $4$。

所有学生的总分为 $T = 7$。注意，各位学生的得分分别为 $2$、$2$、$2$ 和 $1$，满足“排名第 $4$ 的学生恰好得 $1$ 分”的条件。最终，有 $3$ 名学生并列第一，最高得分为 $2$；可以证明，任何其他安排均无法得到更优的结果。