Как профессиональный частный репетитор, Курони должен собирать статистику экзамена. Курони назначил вас для выполнения этой важной задачи. Вы не должны разочаровывать его.
Экзамен состоит из \(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\), и максимально возможное количество баллов для ранга \(1\) при достижении этого максимального числа студентов. Если не существует допустимого расположения, подходящего для данных, выведите \(-1\) \(-1\).
Примечание
Вот один из возможных вариантов для первого примера:
Студенты \(1\) и \(2\) оба решили задачи \(1\) и \(2\).
Студент \(3\) решил задачи \(2\) и \(3\).
Студент \(4\) решил задачу \(4\).
Общая оценка всех студентов составляет \(T = 7\). Обратите внимание, что баллы студентов равны \(2\), \(2\), \(2\) и \(1\) соответственно, что удовлетворяет условию, что ученик с рангом \(4\) получает ровно \(1\) балл. Наконец, \(3\) студента получили максимальный счет \(2\), и можно доказать, что мы не можем добиться большего количества.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 4
2 4
2 3
1 1
0 1
0 0
1
4 1
7
|
3 2
|
|
2
|
5 6
0 6
0 6
2 5
6 6
4 6
1
3 3
30
|
-1 -1
|