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$

题目描述

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.

输入输出格式

输入格式

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

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

说明

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.