Welcome to ZOJ
Select Problem
ZOJ Problem Set - 3650
Toy Blocks

Time Limit: 5 Seconds      Memory Limit: 65536 KB

Kevin and Teresa are brother and sister. Both of them love toy blocks.
As a naughty boy, Kevin always thinks about playing tricks on Teresa. One day, he saw that Teresa had put the toy blocks in particular order. And he decided to push all of them down. Meanwhile, he wants to use the least time so that he can run further to avoid Teresa's angry roar.

So the question is:
There are n toy blocks in a line. Each one has a integer coordinate Xi, and a height Hi. Every second Kevin can choose to push a toy Block i towards the left or right. When Block i being pushed down, some Blocks which are in the same pushing-down direction of Block i can also be pushed down in the same time. ( This costs no time ) If their conditions met, |Xi - Xj| <= Hi(Xj < Xi , if Block i was pushed down towards left;Xj > Xi for towards right), then Block j will be pushed down in the same time.
Notice:We can push Block i1, and Block i1 pushes down Block i2, and Block i2 pushes down Block i3......

Now you have to figure out the least time that Kevin use to make all the blocks down. Some blocks may have same X coordinates.


The input contains with no more that 100 test cases. For each test case:
The first line has a integer n (1 <= n <= 100000)
Then the following n lines. Each line contains two integers Xi and Hi for each toy block. (0 <= Xi <= 2^31 - 1 ,0 <= Hi <= 10^8) If Hi is zero, we still need to push it down


For each test case, output a line.
Output the minimum time(seconds) to make all the blocks down.

Sample Input

1 1
2 2
3 1
5 1
6 1
8 3

Sample output



1st second, Pushing Block 1 towards right can make Block 1 , 2 , 3 down.
2nd second, Pushing Block 6 towards left can make Block 4 , 5 , 6 down.

Author: TANG, YaJie
Submit    Status