← 返回题目列表

Codeforces · 1305/H

H. 私人导师库罗尼

中文机器翻译题面 查看原题

作为一名专业的私人导师,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$$$的最高分并列第一,可以证明我们没有其他安排可以做得更好。