CF1305H Kuroni the Private Tutor

Kuroni 举行了一场考试，有 $n$ 道试题， $m$ 位学生参加的考试，每一题的分值为 1 分。第 $i$ 个问题至少有 $l_i$ 人答对，最多有 $r_i$ 人答对。此外，你还知道所有学生的总成绩为 $t$ 。 你浏览了考试的最终排名，学生的排名从 1 到 $m$ ，第 1 名的学生得分最高，第 $m$ 名的学生得分最低。 同时，你知道排名 $p_i$ 的学生的得分为 $s_i$ 。 Kuroni 希望你回答： - 最多能有多少人并列第一； - 在有尽量多的人并列第一的情况下，第一名的分数最高是多少。

第一行两个整数 $n$ ,$m$ 。 接下来 $n$ 行，每行两个整数，表示 $l_i$ 和 $r_i$ 。 下面一行一个整数 $q$ 。 接下来 $q$ 行，每行两个整数，表示 $p_i$ 和 $s_i$ 。 最后一行一个整数 $t$ 。

一行两个整数，为所求答案，如果无解，请输出 -1 -1 。

$1 \le n$ , $m \le 10^5$ $0 \le l_i \le r_i \le m$ $0 \le q \le m$ $1 \le p_i \le m$ , $0 \le s_i \le n$ $0 \le t \le nm$