作为一名专业的私人导师,Kuroni 必须收集考试的统计数据。库罗尼任命你来完成这项重要任务。你一定不能让他失望。
考试由 $$$n$$$ 个问题组成,已有 $$$m$$$ 名学生参加了考试。每个问题值 $$$1$$$ 分。问题 $$$i$$$ 被至少 $$$l_i$$$ 和最多 $$$r_i$$$ 学生解决。此外,您知道所有学生的总分是 $$$t$$$。
而且,你还看了一眼最后的竞猜排名。学生的排名从$$$1$$$到$$$m$$$,其中$$$1$$$得分最高,$$$m$$$得分最低。关系被任意破坏。
您知道排名 $$$p_i$$$ 的学生的分数为 $$$s_i$$$,$$$1 \le i \le q$$$。
你想知道第一名是否会出现巨大的平局。帮助 Kuroni 确定可以获得与排名 $$$1$$$ 的学生一样多分数的学生的最大数量,以及达到此最大学生数量的排名 $$$1$$$ 的最大可能分数。
输入
第一行输入包含两个整数($$$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$$$),表示所有学生的总分。
输出
输出两个整数:能够获得与排名$$$1$$$一样多分数的学生的最大数量,以及排名$$$1$$$达到此最大学生数量的最大可能得分。如果没有适合给定数据的有效排列,则输出 $$$-1$$$ $$$-1$$$。
示例
输入 #1
5 4 2 4 2 3 1 1 0 1 0 0 1 4 1 7
输出 #1
3 2
输入 #2
5 6 0 6 0 6 2 5 6 6 4 6 1 3 3 30
输出 #2
-1 -1
注意
对于第一个示例,以下是适合数据的一种可能的排列:
学生$$$1$$$ 和$$$2$$$ 都解决了$$$1$$$ 和$$$2$$$ 问题。
学生 $$$3$$$ 解决了问题 $$$2$$$ 和 $$$3$$$。
学生 $$$4$$$ 解决了问题 $$$4$$$。
所有学生的总成绩为$$$T = 7$$$。请注意,学生的分数分别为 $$$2$$$、$$$2$$$、$$$2$$$ 和 $$$1$$$,满足排名 $$$4$$$ 的学生恰好获得 $$$1$$$ 分的条件。最后,$$$3$$$学生以$$$2$$$的最高分并列第一,可以证明我们没有其他安排可以做得更好。