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.