eolymp
bolt
Try our new interface for solving problems
Problems

Объединение интервалов

Объединение интервалов

Time limit 1 second
Memory limit 64 MiB

Для заданного списка целых чисел вам нужно найти n-тое число в списке, когда все числа отсортированы по неубыванию (нумерация индексов начинается с 0). Числа будут заданы интервалами. Каждый интервал будет задан двумя числами, указывающими верхнюю и нижнюю границу интервала (границы интервала также нужно включать в промежуток).

Например, интервалы [1, 3] и [5, 7] задают список чисел {1, 2, 3, 5, 6, 7}. Число может быть задано более чем в одном интервале, например, интервалы [1, 4] и [3, 5] задают собой список чисел {1, 2, 3, 3, 4, 4, 5}.

Input data

В первой строке задано количество интервалов p (1p50), в последующих двух строках заданно по p чисел в каждом: lowerBound и upperBound – нижний и верхний предел интервала (lowerBoundupperbound, -2 *10^9lowerBound, upperBound2 * 10^9.

В последней строке задано число n (0n2 *10^9). Входные данные корректны , n-ый элемент всегда существует.

Output data

Выведите n-тое число в списке, когда все числа отсортированы по неубыванию.

Examples

Input example #1
2
1 5
3 7
4
Output example #1
6