Проиграв все выходные в широко известную игру, в которой садовод-любитель противостоит натиску кровожадных зомби, под вечер воскресенья Марк решает сесть делать уроки на ближайший учебный день. Он открывает тетрадь по русскому языку, пишет число, 'Домашняя работа'... Спустя полчаса Марк выбирается из своих мыслей, в которые он провалился, не успев начать делать первое упражнение. Он понимает, что всё это время его размышления были заняты одним уровнем из его любимой игры, который он никак не может пройти.
На этом уровне все действия происходят на числовой оси $$$OX$$$, направленной слева-направо. Как и во всей игре, на уровне есть нормальные зомби, которые идут справа-налево (в сторону уменьшения своей координаты) со скоростью 1 м/с.
В координате $$$0$$$ стоит дом персонажа игры, который выращивает различные растения, чтобы противостоять нечисти, пытающейся пробраться в его жилище. На этом уровне в его арсенале есть только мухоморы, которые можно заранее посадить в определённых точках числовой прямой.
Встретившись с грибом, нормальный зомби съедает его, разворачивается и идёт направо со скоростью 1 м/с. Если после этого развернувшийся зомби встречается с нормальным, то они аннигилируются и на дальнейший процесс не влияют.
В течение одной секунды происходят следующие действия в заданном порядке:
- Зомби переходят на один метр в том направлении, в котором они шли.
- Если какие-то два зомби (развернувшийся и нормальный) оказываются в одной точке, либо в процессе перехода находились в одной точке, то они аннигилируются.
- Если в точке, где стоит нормальный зомби, растёт мухомор, то гриб съедается, зомби превращается в развернувшегося и со следующей секунды начинает идти направо.
- Если нормальный зомби оказывается в точке $$$0$$$, то игра заканчивается поражением. Если все оставшиеся зомби оказываются развернувшимися — победой, иначе — игра продолжается дальше.
У Марка есть много идей о том, как пройти этот уровень, но ему надо делать уроки. Помогите ему проверить эти идеи, сказав, через сколько секунд после начала все оставшиеся зомби окажутся развернувшимися, либо огорчите его, сказав, что садовод не сможет сохранить свои мозги в неприкосновенности.
В первой строке вводится единственное целое число $$$n$$$ ($$$2 \le n \le 2\cdot10^6$$$) — общее количество мухоморов и зомби, расположенных на числовой прямой в момент запуска.
В следующих $$$n$$$ строках вводятся по $$$2$$$ целых числа $$$t_i$$$ и $$$x_i$$$ ($$$t_i \in \{0, 1\}$$$, $$$0 \le x \le 10^9$$$) — тип игрового объекта ($$$0$$$ для нормального зомби и $$$1$$$ для мухомора) и его координата на числовой прямой в начальный момент времени. Гарантируется, что $$$x_i \lt x_{i + 1}$$$.
В единственной строке выведите, через сколько секунд после начала все оставшиеся зомби станут развернувшимися, если такой момент наступит, либо «The zombies ate your brains!», если какой-то нормальный зомби сможет добраться до дома.
31 40 50 8
3
71 11 30 60 81 90 120 14
4
41 10 30 50 7
The zombies ate your brains!
Объём входных данных в данной задаче велик, поэтому при написании решения настоятельно рекомендуется использовать оптимизации ввода/вывода.
| Name |
|---|