Rick and Morty are invited for a meeting at planet Gazorpazorp. So they want to travel from Earth to Gazorpazorp and back. Now on their way to Gazorpazorp, they encounter N space stations, at various locations. These space stations are of two types - type1 and type2. Type 1 allows multiple visits, while Type 2 allows at most one visit.
Now you have to help Rick and Morty find a stratergy, such that the maximum distance they travel without visiting any space station is minimised.
Note: They can visit type 2 space stations at most one time on the entire round trip(Earth -> Gazorpazorp -> Earth), but can visit type 1 space stations as many times as they like.
Input:
The first line contains 2 integers -N,D- the number of space stations and distance between Earth and Gazorpazorp.
Next N line contains 2 integer - t,d- denoting that type t (1 or 2) space station is present at distance d from Earth.
Output:
Print a single integer, the minimized maximum distance they travel without visiting any space station.
Constraint:
0<=N<=100000
1<=D<=1000000000
1<=t<=2
1<=d<D
Setter: Kunal Khatri
The optimal strategy for this case is to visit space station at distance 3 and space station at distance 6 while going from earth to Gazorpazorp and visit space station 3 while coming back.
Note: you cannot visit space station at distance 6 while coming back as it is a type 2 space station and so it allows at most 1 visit.
