피트의 활

면접 대비

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

요약

n개의 구간 [x_i - d_i, x_i + d_i]을 모두 포함하는 가장 큰 점 X를 구합니다. 그런 점이 없으면 -1을 출력합니다.

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

문제

피트는 자신의 활을 키틱스에게 자랑하고 싶어 한다. 활에서 가장 중요한 것은 사거리이다.

활이 얼마나 멀리 나가는지 보여 주기 위해 피트는 좌표 $0$ 에 서서 직선 방향으로 화살을 쏘았다. 화살은 그 직선 위의 점 $X$ 에 떨어졌다. 피트는 $X$ 를 알고 있으며, 키틱스에게 이를 알아내 보라고 한다. 그는 키틱스에게 $x_i$ $d_i$ 형태의 힌트 $n$ 개를 주었다. 이는 점 $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$ 를 한 줄에 출력한다. 그런 $X$ 가 없으면 -1을 출력한다.

예제3

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

예제 3

입력

예상 출력