Лук Пита

시간 제한2초메모리 제한1024 MB

요약

각 단서가 |X - x_i| <= d_i 형태로 주어질 때 모든 단서를 만족하는 가장 큰 정수 X를 구하고, 없으면 -1을 출력한다.

난이도: 쉬움10점 중 3점
유형: 구간, 구현, 수학
정답자: 아직 제출이 없습니다

문제

Пит хочет похвастаться своим луком перед Китнисс. Конечно же, самое главное в луке --- это дальность стрельбы.

Чтобы показать Китнисс, насколько далеко стреляет его лук, Пит встал в точку с координатой $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$ , удовлетворяющего всем подсказкам Пита.

예제3

예제 1
입력
```
2
1 2
3 2
```
예상 출력
```
3
```
예제 2
입력
```
3
2 2
6 2
8 1
```
예상 출력
```
-1
```

예제 3

입력

예상 출력