10265: CF EDU - Binary Search - Step 5 - A. K-th Number in the Union of Segments
[Creator : ]
Description
Given $n$ segments of integers $[l_1,r_1], [l_2,r_2], ..., [l_n,r_n]$.
Let's write out all the numbers from these segments into an array. If some number contains in more than one segment, then it must appear so many times in the array, how many segments it contains. That is, the length of the array is equal to the sum the number of numbers in all segments.
After that, the array is sorted. Your task is to find the number at the position $k$ (numbering starts from 0) in it.
Input
The first line contains integers $n,k\ (1≤n≤50,\ 0≤k≤2⋅10^9)$.
In the next $n$ lines segments are given in the form of pairs $l_i,r_i\ (−2⋅10^9≤l_i≤r_i≤2⋅10^9)$. It is guaranteed that the $k$-th number in the union exists.
Output
Print the required value.
Sample 1 Input
2 4
1 3
5 7
Sample 1 Output
6
Sample 2 Input
2 3
1 4
3 5
Sample 2 Output
3
Sample 3 Input
1 1500000091
-1500000000 1500000000
Sample 3 Output
91