Problem: Protection of the Indian border and safe transport of items from one point to another along the border are the paramount jobs for the Indian army. However they need some information about the protection status along the length of the border. The border can be viewed as the real x-axis. Along the axis, Indian army has N checkpoints for lookout. 
We know that each checkpoint is located at an integer location xi. Each checkpoint must have a fleet of armed men which are responsible for guarding the neighboring areas of the checkpoint and provide military assistance of all kinds. The size of the fleet is based on the location of the checkpoint and how active the region is for terrorist activities.

Given the number of armed men assigned at the i^th checkpoint, as pi, this information is available for all checkpoints. 
With the skills of the armed men, it is known that if for the i^th checkpoint, the length on the x axis that they can defend is a closed interval [xi-pi, xi+pi].
Now, your task is to transport some military items from position S to the end position E on the x-axis.
Input:
First line of the input contains 3 integers N, S and E. N is the number of checkpoints that the Indian Army has on the border.
Then N lines follow. i^th line contains 2 integers, xi and pi.

Output:
Print the total distance of the x-axisfrom S to E, that is not protected by the armed forces.

Constraints:
1 ≤ N ≤ 10^5
1 ≤ xi, pi ≤ 10^18
xi + pi ≤ 10^18
1 ≤ S ≤ E ≤ 10^18

SAMPLE INPUT
5 229 8419
1795 95
4873 720
3149 81
6101 2325
3674 629

SAMPLE OUTPUT
2626

Solution (in PYTHON):

Solution:
__author__ = 'apritam'


def is_in_range(value , start, end):
    if value >=start and value <=end:
        return True
    return False

test_case_input=raw_input()
n_s_e_list=test_case_input.split(' ')
number_of_check = long(n_s_e_list[0])
index = 0;
l=[];
#l.append([int(n_s_e_list[1]),int(n_s_e_list[2])])

while index < number_of_check:
    x_strength = raw_input()
    x_s_list=x_strength.split(' ')
    if long(x_s_list[0])>long(x_s_list[1]):
        l.append([long(x_s_list[0])-long(x_s_list[1]),long(x_s_list[0])+long(x_s_list[1])])
    elif long(x_s_list[0])<=long(x_s_list[1]):
        l.append([0,long(x_s_list[0])+long(x_s_list[1])])
    index+=1

def getKey(item):
    return item[0]

l=sorted(l, key=getKey)

length=l.__len__()
i=0
result = 0
merged = []
max_cov=0
min_cov=-1
end = long(n_s_e_list[2])
start = long(n_s_e_list[1])
max_cov= 0

def get_merged_set(l):
    rl = []
    i=0
    while i<l.__len__()-1:
        if is_in_range(l[i][1],l[i+1][0],l[i+1][1]):
            rl.append([l[i][0],l[i+1][1]])
            i+=1
        elif l[i][1] > l[i+1][1]:
            rl.append([l[i][0],l[i][1]])
            i+=1
        else:
            rl.append([l[i][0],l[i][1]])
            if(i==l.__len__()-2):
                rl.append([l[i+1][0],l[i+1][1]])
        i+=1
    if all(x in rl for x in l):
        return rl
    else:
        return get_merged_set(rl)


def get_merged(l):
    rl = []
    rl.append([l[0][0],l[0][1]])
    i=0
    while i<=l.__len__()-1:
        if (rl[rl.__len__()-1][1] < l[i][0]-1):
            rl.append([l[i][0],l[i][1]])
        elif (rl[rl.__len__()-1][1] < l[i][1]):
            x= rl[rl.__len__()-1][0]
            rl.pop()
            rl.append([x,l[i][1]])
        i+=1
    return rl

if length > 1:
    l=get_merged(l)

i = 0
result = end-start
covered = 0

while i<= l.__len__()-1:
    if (is_in_range(l[i][1],start,end) or is_in_range(l[i][0],start,end)) and start<end:
        if is_in_range(l[i][1],start,end) and is_in_range(l[i][0],start,end):
            covered += l[i][1]-l[i][0]
            start=l[i][1]
        elif is_in_range(l[i][1],start,end):
            if start >= l[i][0]:
                covered += l[i][1]-start
            else:
                covered += l[i][1]-l[i][0]
            start=l[i][1]
        else:
            if end >= l[i][1]:
                covered +=  l[i][1]-l[i][0]
                start = l[i][1]
            else:
                covered +=  end-l[i][0]
                start = end
    i+=1
print result-covered