B. Коридор или туда и обратно
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы находитесь в бесконечном коридоре, который простирается бесконечно вправо и разделен на квадратные комнаты. Вы начинаете в комнате $$$1$$$, перемещаетесь в комнату $$$k$$$ и затем возвращаетесь в комнату $$$1$$$. Вы можете выбрать значение $$$k$$$. Переход в соседнюю комнату занимает $$$1$$$ секунду.

Кроме того, в коридоре находится $$$n$$$ ловушек: $$$i$$$-я ловушка находится в комнате $$$d_i$$$ и активируется через $$$s_i$$$ секунд после вашего входа в комнату $$$\boldsymbol{d_i}$$$. После активации ловушки вы не можете ни войти в комнату с этой ловушкой, ни выйти из неё.

Схематическое изображение возможного коридора и вашего пути к комнате $$$k$$$ и обратно.

Определите максимальное значение $$$k$$$, которое позволяет вам безопасно переместиться из комнаты $$$1$$$ в комнату $$$k$$$ и затем вернуться в комнату $$$1$$$.

Например, если $$$n=1$$$ и $$$d_1=2, s_1=2$$$, вы можете переместиться в комнату $$$k=2$$$ и вернуться безопасно (ловушка активируется в момент $$$1+s_1=1+2=3$$$, она не может помешать вам вернуться назад). Но если вы попытаетесь достичь комнаты $$$k=3$$$, ловушка активируется в момент $$$1+s_1=1+2=3$$$, что помешает вашему возвращению (вы попытаетесь войти в комнату $$$2$$$ на обратном пути в $$$3$$$ секунду, но активированная ловушка заблокирует вас). Любое большее значение для $$$k$$$ также невозможно. Таким образом, ответом является $$$k=2$$$.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора содержит целое число $$$n$$$ ($$$1 \le n \le 100$$$) — количество ловушек.

Следующие $$$n$$$ строк каждого набора содержат по два целых числа $$$d_i$$$ и $$$s_i$$$ ($$$1 \le d_i, s_i \le 200$$$) — параметры ловушки (вы должны покинуть комнату $$$d_i$$$ строго до того, как пройдет $$$s_i$$$ секунд с момента входа в эту комнату). Возможно, что несколько ловушек могут находиться в одной комнате (значения $$$d_i$$$ могут повторяться).

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

Для каждого набора входных данных выведите максимальное значение $$$k$$$, которое позволяет вам переместиться в комнату $$$k$$$ и вернуться в комнату $$$1$$$ без столкновения с активной ловушкой.

Пример
Входные данные
7
1
2 2
3
2 8
4 3
5 2
1
200 200
4
1 20
5 9
3 179
100 1
2
10 1
1 18
2
1 1
1 2
3
1 3
1 1
1 3
Выходные данные
2
5
299
9
9
1
1
Примечание

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

Во втором наборе входных данных вторая ловушка мешает вам достигнуть $$$k\ge6$$$. Если $$$k\ge6$$$, вторая ловушка активируется в момент $$$3+s_2=3+3=6$$$ (время, когда вы входите в комнату $$$4$$$ плюс $$$s_2$$$). В случае $$$k\ge6$$$ вы вернетесь в комнату $$$4$$$ в момент времени $$$7$$$ или позже. Ловушка будет активна в это время. Можно показать, что комната $$$k=5$$$ может быть достигнута без столкновения с активной ловушкой.

В третьем наборе входных данных примера вы можете добраться до комнаты $$$299$$$ и сразу вернуться в комнату $$$1$$$.