KGF - KJ and street lights

Kartik Joshi (KJ) has a very beautiful girlfriend,  Priyanka Sharma (PS). (hehe  :P)

She's very possessive and calls KJ and asks him to come tonight at her home to ( most probably) meet.

 

KJ and PS lives on  x - axis. KJ's house is located on 0 and PS's house is located on  p (a positive integer).
There is only one road through which people can travel i.e. the x - axis. There are n street lights on the x -axis. The ith street light is situated at  xi and has a characteristic  ri so that it can spread light in the range
[xi - ri, xi + ri] . The street lights emit rays which are self destructive in nature, which means that if there
is some co-ordinate of road receiving light from more than one  street lights, then the light on that coordinate vanishes, i.e. that co-ordinate remains dark.

KJ and PS live on x - axis. KJ's house is located on 0 and PS's house is located on p (a positive integer). There is only one road through which people can travel i.e. the x-axis. There are n street lights on the x-axis.

The ith street light is situated at xi and has a characteristic ri so that it can spread light in the range [xi - ri, xi + ri] . The street lights emit rays which are self-destructive in nature, which means that if there

are some co-ordinate of road receiving light from more than one street lights, then the light on that coordinate vanishes, i.e. that co-ordinate remains dark.

We all know that KJ is a  kid and is afraid of the dark. So he wishes to know beforehand the maximum

continuous number of integer co-ordinates he has to travel in the dark while going from his home

to PS's home. Help him find the answer!

Note: there may be more than one street light on the same integer co-ordinates. Also note that KJ always

moves in the direction of PS's house.

Input Format

The first line contains two space-separated integers  n and  p, the number of street lights and the position

of PS's house on the x-axis.

The next n lines contain two space-separated integers,  xi and  ri, the position of the  ith street light and

the characteristic of the ith street light.

Constraints

1 <= p <= 2,00,000

0 <= n <= 2,00,000

0 <= xi <= p

0 <= ri <= 2,00,000

Output Format

Output a single integer, the maximum number of continuous integer co-ordinates KJ has to travel in the

dark while going from his house on 0 to PS's house on  p.

Sample Input 0

4 4

1 2

3 0

0 2

3 0

Sample Output 0

 

5

Explanation 0

The points lit by first street light are : {0, 1, 2, 3}


The points lit by second street light are: {3}

The points lit by third street light are: {0, 1, 2}

The points lit by fourth street light are: {3}

So, the points: {0, 1, 2, 3} will receive light from more than one street light and hence will remain dark,

also, the point {4} doesn't receive light from any of the street lights, so it will also remain dark. Hence the


maximum continuous integer points that will remain dark are {0, 1, 2, 3, 4}. So, the answer is 5.



Added by:Prodip
Date:2019-04-06
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.