SOLVE
LATER
Pussycat Sonya placed N sticks on a straight line. The i-^{th} stick is located at position \(x_i\) and has height \(h_i\). There are no two sticks located at the same position. Sonya can push sticks to make them fall to the left or the right side. While falling, a stick can touch its neighbors and make them also fall in the same direction (like dominoes).
More formally: if a stick at position x with height h is falling to the \(\mathit{left}\), it will make all the sticks at positions \((x - h) \dots x\) inclusive fall to the left. Similarly, if a stick is falling to the \(\mathit{right}\) it will make all the sticks at positions \(x...(x + h)\) inclusive fall to the right.
Now Sonya is interested in finding the minimal number of sticks she needs to push to make all N sticks fall.
Input format:
The first line contains one integer N \(-\) the number of sticks.
Each of the next N lines contains two integers \(x_i, h_i\) \(-\) position and height of the i-^{th} stick.
Output format:
Print the minimal number of sticks Sonya needs to push.
Constraints
\(1 \leq N \leq 5 \cdot 10^5\)
\(1 \leq x_i, h_i \leq 2 \cdot 10^9\)
15 points
\(1 \leq N \leq 10\)
10 points
\(1 \leq N \leq 300\)
10 points
\(1 \leq N \leq 5000\)
65 points
Original constraints
The optimal solution is to push the stick at position 1 to the right. It will also make the stick at position 3 fall.
And then push stick at position 9 to the left. It will make the stick at position 7 fall to the left, which will cause the stick at position 6 to also fall to the left.