Farmer John has received a shipment of N large hay bales (1 <= N <= 4000) and placed them at various locations along the road. Bessie the cow is out grazing along the road, and may now be trapped within the bales!

Each bale j has a size S_j and a distinct position P_j along the one-dimensional road. Bessie starts at some location where there is no hay bale, and can move freely along the road up to the position of a bale, but cannot cross through it. 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. After doing this, she might open up more space to break through other bales.

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

Line 1: N. Each of the next N lines describes a bale with two integers: its size and position, each in the range 1...10^9.

A single integer giving the area of the road from which Bessie cannot escape.

riseoj 작성

출처 올림피아드 > USACO > 2014-2015 > US Open > Bronze