뽀삐 구하기

실행 시간 제한	메모리 제한
1 초	256 MB

📃 해결할 문제

김민수는 아파트 단지의 길에 큰 상자 N개를 배치했습니다. 그런데 그는 상자 사이에서 산책 중인 개 뽀삐가 상자들에 의해 갇힐 수 있다는 것을 깜빡하고 말았습니다.

상자는 각각 다른 크기와 위치를 가지고 있습니다. 뽀삐는 상자가 없는 곳에서 시작하여 길을 따라 이동할 수 있습니다. 하지만 상자 앞에 도달하면 그 위치를 넘어서는 것은 할 수 없습니다. 단, 뽀삐가 일정 거리 D를 같은 방향으로 달려가면, 그는 D보다 작은 크기의 상자를 부술 수 있는 힘을 얻게 됩니다.

뽀삐가 탈출하려면 길의 가장 왼쪽 또는 오른쪽 끝에 있는 상자를 부셔야 합니다. 뽀삐가 탈출할 수 없는 길의 구간을 찾아주세요.

예를 들어, 아파트 단지의 길에는 5개의 상자가 있고, 뽀삐가 상자가 위치한 1과 5 사이에서 시작한다면, 4의 거리만큼 탈출할 수 없게 됩니다.

💻 입력

입력의 첫 번째 줄에는 N이 주어집니다. 다음 N개의 줄 각각은 상자를 설명하며, 크기와 위치를 나타내는 두 정수가 포함됩니다. 각 값은 1…10^9 범위 안에 있습니다.

🖨️ 출력

뽀삐가 탈출할 수 없는 길의 영역을 나타내는 하나의 정수를 출력해주세요.

💻 예제 입력 1

🖨️ 예제 출력 1

💡 힌트

1~4 사이에서 시작한다고 가정합니다.
뽀삐는 3의 거리를 달려서 크기 1의 상자를 파괴할 수 있습니다. 그런 다음 4~8 사이로 진입하여 4의 거리를 달려 크기 8의 상자까지 닿지만, 파괴할 수는 없습니다. 왼쪽 끝의 상자도 크기가 8이므로 뽀삐는 탈출할 수 없습니다. 그래서 1~4의 넓이 3이 뽀삐가 탈출하지 못하는 지역입니다.

4~8 사이에서 시작한다고 가정합니다.
뽀삐는 4의 거리를 달려서 오른쪽의 크기 8 상자까지 닿지만, 파괴할 수 없습니다. 왼쪽 끝의 상자도 크기가 8이므로 뽀삐는 탈출할 수 없습니다. 그래서 4~8의 넓이 4가 뽀삐가 탈출하지 못하는 지역입니다.

8~15 사이에서 시작한다고 가정합니다.
뽀삐가 어느 방향으로 달려가든 끝에 도달하기 전에 크기 7 또는 크기 8의 상자를 만납니다. 따라서 뽀삐는 이 구간에서도 탈출할 수 없습니다. 8~15의 넓이는 7입니다.

15~20 사이에서 시작한다고 가정합니다.
뽀삐는 5의 거리를 달려 크기 4의 상자를 파괴할 수 있습니다. 그러므로 15~20 구간에서 뽀삐는 탈출할 수 있습니다.

따라서 뽀삐가 탈출할 수 없는 전체 지역은 3 + 4 + 7 = 14입니다.

출처: USACO 2015 US Open, Bronze Problem 3. Trapped in the Haybales (Bronze)