H. Курони, частный репетитор
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Как профессиональный частный репетитор, Курони должен собирать статистику экзамена. Курони назначил вас для выполнения этой важной задачи. Вы не должны разочаровывать его.

Экзамен состоит из $$$n$$$ вопросов, и $$$m$$$ студентов сдали экзамен. За каждый вопрос давали $$$1$$$ балл. Вопрос $$$i$$$ был решен не менее $$$l_i$$$ и не более $$$r_i$$$ студентами. Кроме того, вы знаете, что общий балл всех студентов составляет $$$t$$$.

Кроме того, вы взглянули на окончательный рейтинг в викторине. Студенты были оценены от $$$1$$$ до $$$m$$$, где ранг $$$1$$$ имеет самый высокий балл, а ранг $$$m$$$  — самый низкий балл. В случае равенства количества баллов студенты были упорядочены произвольно.

Вы знаете, что ученик с рангом $$$p_i$$$ получил оценку $$$s_i$$$ для $$$1 \le i \le q$$$.

Вы задались вопросом, могло ли много студентов не поделить первое место. Помогите Курони определить максимальное количество студентов, которые могли набрать столько же баллов, сколько студент с рангом $$$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$$$.

Примеры
Входные данные
5 4
2 4
2 3
1 1
0 1
0 0
1
4 1
7
Выходные данные
3 2
Входные данные
5 6
0 6
0 6
2 5
6 6
4 6
1
3 3
30
Выходные данные
-1 -1
Примечание

Вот один из возможных вариантов для первого примера:

Студенты $$$1$$$ и $$$2$$$ оба решили задачи $$$1$$$ и $$$2$$$.

Студент $$$3$$$ решил задачи $$$2$$$ и $$$3$$$.

Студент $$$4$$$ решил задачу $$$4$$$.

Общая оценка всех студентов составляет $$$T = 7$$$. Обратите внимание, что баллы студентов равны $$$2$$$, $$$2$$$, $$$2$$$ и $$$1$$$ соответственно, что удовлетворяет условию, что ученик с рангом $$$4$$$ получает ровно $$$1$$$ балл. Наконец, $$$3$$$ студента получили максимальный счет $$$2$$$, и можно доказать, что мы не можем добиться большего количества.