eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

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

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

Лимит времени 1 секунда
Лимит использования памяти 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}.

Входные данные

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

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

Выходные данные

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

Пример

Входные данные #1
2
1 5
3 7
4
Выходные данные #1
6