| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 40 | 34 | 23 | 92.000% |
Пит хочет похвастаться своим луком перед Китнисс. Конечно же, самое главное в луке --- это дальность стрельбы.
Чтобы показать Китнисс, насколько далеко стреляет его лук, Пит встал в точку с координатой 0ドル$ и выстрелил по прямой. Стрела упала в точку $X$ прямой, по которой стрелял Пит. Пит знает число $X,ドル и предлагает выяснить его Китнисс. Для этого он дал Китнисс $n$ подсказок вида: $x_i$ $d_i,ドル означающих, что точка $x_i$ находится от точки $X$ на расстоянии не более чем $d_i$.
Теперь по этой информации Китнисс хочет выяснить, какое наибольшее $X$ удовлетворяет всем подсказкам Пита.
В первой строке содержатся одно натуральное число $n$ (1ドル \le n \le 10^5$).
В следующих $n$ строках содержатся по два целых числа $x_i$ $d_i$ (0ドル \le x_i \le 10^9,ドル 0ドル \le d_i \le 10^9$).
В единственной строке выведите наибольшее $X,ドル удовлетворяющее всем подсказкам Пита, либо \text{ ---1}, если не существует $X,ドル удовлетворяющего всем подсказкам Пита.
2 1 2 3 2
3
3 2 2 6 2 8 1
-1
5 100 97 115 104 97 115 111 115 107 97
197