A. Подстроено!
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Монокарп организует соревнование по тяжелой атлетике. В соревновании участвуют $$$n$$$ спортсменов, сила $$$i$$$-го спортсмена равна $$$s_i$$$, а его выносливость равна $$$e_i$$$. Спортсмен под номером $$$1$$$ — Поликарп, друг Монокарпа, и Монокарп очень хочет, чтобы Поликарп победил.

Соревнование будет проводиться следующим образом. Жюри выберет положительное (больше нуля) целое число $$$w$$$, которое обозначает вес штанги, используемой в соревновании. Цель каждого спортсмена — поднять штангу как можно больше раз. Спортсмен, который поднимет штангу наибольшее количество раз, будет объявлен победителем (если есть несколько таких спортсменов — победителя нет).

Если вес штанги $$$w$$$ строго больше силы $$$i$$$-го спортсмена $$$s_i$$$, то $$$i$$$-й спортсмен не сможет поднять штангу ни разу. В противном случае $$$i$$$-й спортсмен сможет поднять штангу, и количество раз, которое он это сделает, будет равно его выносливости $$$e_i$$$.

Например, предположим, что есть $$$4$$$ спортсмена с параметрами $$$s_1 = 7, e_1 = 4$$$; $$$s_2 = 9, e_2 = 3$$$; $$$s_3 = 4, e_3 = 6$$$; $$$s_4 = 2, e_4 = 2$$$. Если вес штанги равен $$$5$$$, то:

  • первый спортсмен сможет поднять штангу $$$4$$$ раза;
  • второй спортсмен сможет поднять штангу $$$3$$$ раза;
  • третий спортсмен не сможет поднять штангу;
  • четвертый спортсмен не сможет поднять штангу.

Монокарп хочет выбрать $$$w$$$ таким образом, чтобы Поликарп (спортсмен под номером $$$1$$$) выиграл соревнование. Помогите ему выбрать значение $$$w$$$, или сообщите, что это невозможно.

Входные данные

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$2 \le n \le 100$$$) — количество спортсменов. Затем следуют $$$n$$$ строк, $$$i$$$-я из которых содержит два целых числа $$$s_i$$$ и $$$e_i$$$ ($$$1 \le s_i \le 10^9$$$; $$$1 \le e_i \le 100$$$) — сила и выносливость $$$i$$$-го спортсмена.

Выходные данные

Для каждого набора входных данных выведите ответ следующим образом:

  • если ответ существует, выведите одно целое число — значение $$$w$$$, удовлетворяющее ограничениям. Выведенное целое число должно удовлетворять условию $$$1 \le w \le 10^9$$$. Можно показать, что если ответ существует, то существует хотя бы одно такое значение $$$w$$$. Если ответов несколько, вы можете вывести любой из них;
  • в противном случае выведите одно целое число $$$-1$$$.
Пример
Входные данные
3
4
7 4
9 3
4 6
2 2
2
4 6
100 100
2
1337 3
1337 3
Выходные данные
5
-1
-1
Примечание

Первый набор входных данных примера разобран в условии.