Вы находитесь в бесконечном коридоре, который простирается бесконечно вправо и разделен на квадратные комнаты. Вы начинаете в комнате \(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\).
Выходные данные
Для каждого набора входных данных выведите максимальное значение \(k\), которое позволяет вам переместиться в комнату \(k\) и вернуться в комнату \(1\) без столкновения с активной ловушкой.
Примечание
Первый набор входных данных примера разобран в условии задачи выше.
Во втором наборе входных данных вторая ловушка мешает вам достигнуть \(k\ge6\). Если \(k\ge6\), вторая ловушка активируется в момент \(3+s_2=3+3=6\) (время, когда вы входите в комнату \(4\) плюс \(s_2\)). В случае \(k\ge6\) вы вернетесь в комнату \(4\) в момент времени \(7\) или позже. Ловушка будет активна в это время. Можно показать, что комната \(k=5\) может быть достигнута без столкновения с активной ловушкой.
В третьем наборе входных данных примера вы можете добраться до комнаты \(299\) и сразу вернуться в комнату \(1\).
Примеры
| № | Входные данные | Выходные данные |
|
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
|