Merging Intervals
Given a list of integer intervals, your task is to determine the n-th number in the list when all numbers are sorted in non-decreasing order (with indexing starting from 0). Each interval is defined by two numbers, representing the inclusive lower and upper bounds of that interval.
For instance, the intervals [1, 3] and [5, 7] correspond to the list of numbers {1, 2, 3, 5, 6, 7}. Note that a number can appear in multiple intervals: for example, the intervals [1, 4] and [3, 5] yield the list {1, 2, 3, 3, 4, 4, 5}.
Input
The first line contains an integer p (1 ≤ p ≤ 50), representing the number of intervals. The following p lines each contain two integers: lowerBound and upperBound, which define the bounds of an interval. It is guaranteed that lowerBound ≤ upperBound and -2 * 10^9 ≤ lowerBound, upperBound ≤ 2 * 10^9.
The final line contains the integer n (0 ≤ n ≤ 2 * 10^9). The input is guaranteed to be valid, meaning the n-th element always exists.
Output
Print the n-th number in the list when all numbers are sorted in non-decreasing order.