문제

동희는 충남대학교 캠퍼스 내의 직선 도로를 따라 $N$개의 대형 볏짚을 배치했다 ($1 \le N \le 100\,000$). 그런데 도로에서 산책 중이던 우솔이가 볏짚들 사이에 갇혔을 수도 있다는 사실을 동희는 깜빡 잊고 말았다!

각 볏짚 $j$는 크기 $S_j$와 위치 $P_j$를 가진다. 우솔이는 도로 위를 자유롭게 이동할 수 있으며 볏짚이 있는 위치까지 갈 수 있지만, 볏짚을 통과해서 지나갈 수는 없다. 예외적으로, 우솔이가 한 방향으로 거리 $D$만큼 연속해서 달리면, 크기가 $D$보다 작은 볏짚을 부수고 영구적으로 제거할 수 있는 충분한 속도를 얻는다. 볏짚을 제거하면 공간이 더 넓어져 다른 볏짚을 향해 달려가 부수는 것도 가능해진다.

우솔이가 결국 맨 왼쪽 혹은 맨 오른쪽 볏짚을 부수는 데 성공하면 탈출할 수 있다. 우솔이가 탈출할 수 없는 실수(real-valued) 시작 위치들의 총 길이를 구하시오.

입력

첫째 줄에 볏짚의 개수 $N$이 주어진다. ($1 \le N \le 100\,000$)

이어서 $N$개의 줄에 각 볏짚의 크기 $S_j$와 위치 $P_j$가 공백으로 구분되어 주어진다. ($1 \le S_j, P_j \le 10^9$) 모든 위치는 서로 다르다.

출력

우솔이가 탈출할 수 없는 도로의 총 길이를 나타내는 정수 하나를 출력한다.

예제 입력 1

5
8 1
1 4
8 8
7 15
4 20

예제 출력 1

14