페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#3930

Trapped in the Haybales 1초 256MB

문제

Farmer John has received a shipment of N large hay bales (1 \le N \le 100,000), and placed them at various locations along the road leading to his barn. Unfortunately, he completely forgets that Bessie the cow is out grazing along the road, and she may now be trapped within the bales!

Each bale j has a size S_j and a position P_j giving its location along the one-dimensional road. Bessie the cow can move around freely along the road, even up to the position at which a bale is located, but she cannot cross through this position. As an exception, if she runs in the same direction for D units of distance, she builds up enough speed to break through and permanently eliminate any hay bale of size strictly less than D. Of course, after doing this, she might open up more space to allow her to make a run at other hay bales, eliminating them as well.

Bessie can escape to freedom if she can eventually break through either the leftmost or rightmost hay bale. Please compute the total area of the road consisting of real-valued starting positions from which Bessie cannot escape.

[Problem credits: Brian Dean, 2015]


입력

The first line of input contains N. Each of the next N lines describes a bale, and contains two integers giving its size and position, each in the range 1\ldots 10^9. All positions are distinct.


출력

Print a single integer, giving the area of the road from which Bessie cannot escape.


예제1

입력
5
8 1
1 4
8 8
7 15
4 20
출력
14

출처

USACO 2015 US Open Gold

역링크 공식 문제집만