Zcmu--5066: dark corridor

Description

Late at night , Small Q Walking on a dark corridor . The corridor can be regarded as a number axis . There are n Lights , From left to right
The number is 1 To n, The first i The coordinates of the lamp are xi, It can illuminate the number axis [xi − ri, xi + ri] Part of （ Including both sides ）. If one
The position is not illuminated by any lights , So afraid of the dark little Q I dare not go there .
Small Q You can go left or right on the corridor . If his position coincides with a light , He can choose to turn it on or off
The lamp . In limine , Small Q The position of is the same as that of 1 Lamp coincidence , The first 1 A light is on , All other lights are off . Small
Q I hope to walk to the... Under the light n Location of lights , And make the n A light is on , All other lights are off .
Please write a program , Help small Q Find the shortest route , Or tell him it's impossible .

Input

The first line contains a positive integer T(1 ≤ T ≤ 2000), Number of groups representing test data .
The first row of each set of data contains a positive integer n(2 ≤ n ≤ 100000), Indicates the number of lights .
Next n That's ok , Two positive integers per line xi, ri, Indicate the position and light radius of each lamp respectively , among
1 ≤ x1 < x2 < x3 < ::: < xn ≤ 109,1 ≤ ri ≤ 109.
Input data guarantee Σn ≤ 300000.

Output

For each group of data, output a line and an integer , That is, the shortest total distance , If there is no solution, please output “-1”.

Sample Input

4

5

1  5

3  1

4  9

7  8

8  4

2

1  1

10  10

2

1  10

10  8

2

1  1000000000

1000000000  999999999

Sample Output

21

-1

-1

2999999997

analysis ： Through the example, we can find “ As if ” The shortest path is ( End - The starting point )*3, Because if we can get to the next point , There must be a light in front , If we go to a point every time and turn off the front immediately , It must be a long way to go back and forth , It should be the last time to go back and turn off all the other lights twice .

            Conclusion ： If we can reach the end and go back to the starting point , So the answer is ( End - The starting point )*3, Otherwise, it would be -1. 

#include <stdio.h>
struct su
{
	long long x,r;	// Save the coordinates and lighting radius of each lamp  
}a[100005];
int main()
{
	long long t,m,s,n,i;
	scanf("%lld",&t);
	while(t--){
		s=1; 	//s To record whether we can reach the end or the starting point  
		scanf("%lld%lld%lld",&n,&a[0].x,&a[0].r);
		m=a[0].x+a[0].r;	// The farthest place you can reach at the beginning  
		for(i=1;i<n;i++){	// Judge whether we can reach the end ！！！！！！！！！！！ 
			scanf("%lld%lld",&a[i].x,&a[i].r);
			if(s==0) continue;	// If you can't reach the next light , I.e. unable to reach  
			if(a[i].x<=m&&a[i].x+a[i].r>m) m=a[i].x+a[i].r;	// Update the farthest place  
			else if(a[i].x>m) s=0;	// Can't get to the next point  
		}	
		if(s==0){
			printf("-1\n");
			continue;
		}
		m=a[n-1].x-a[n-1].r;	// Go back to the left , Is the cut radius , Other same as above  
		for(i=n-2;i>=0;i--){ // Judge whether you can return to the starting point ！！！！！！！！！！！  
			if(s==0) continue;
			if(a[i].x>=m&&a[i].x-a[i].r<m) m=a[i].x-a[i].r;
			else if(a[i].x<m) s=0;
		}
		if(s==0) printf("-1\n");
		else printf("%lld\n",(a[n-1].x-a[0].x)*3);
	}
}