문제

서현이는 일직선으로 뻗은 도로 위에 있다. 도로에는 $N$개의 장애물이 놓여 있으며, 각 장애물 $j$는 크기 $S_j$와 서로 다른 위치 $P_j$를 가진다. ($1 \le N \le 4\,000$; $1 \le S_j, P_j \le 10^9$)

서현이는 장애물이 없는 위치에서 시작하여 도로 위를 자유롭게 이동할 수 있다. 장애물이 있는 위치까지 갈 수는 있지만, 그 위치를 지나쳐 갈 수는 없다. 단, 서현이가 한 방향으로 거리 $D$만큼 연속해서 달리면, 크기가 $D$보다 작은 장애물을 부수고 영구적으로 제거할 수 있다. 장애물을 제거한 후에는 더 넓은 공간을 확보할 수 있어, 이를 이용해 다른 장애물을 추가로 부술 수도 있다.

서현이가 가장 왼쪽에 있는 장애물이나 가장 오른쪽에 있는 장애물을 부수고 밖으로 나갈 수 있다면 탈출에 성공한 것으로 간주한다. 서현이가 탈출할 수 없는 실수(real-valued) 시작 위치들의 총 길이를 구하는 프로그램을 작성하시오. 예를 들어, 위치 $1$과 위치 $5$에 있는 장애물 사이의 모든 지점에서 탈출할 수 없다면, 이 구간의 길이는 $4$가 된다.

입력

첫째 줄에 장애물의 개수 $N$이 주어진다. ($1 \le N \le 4\,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