D. Целевое заражение
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Даны $$$n$$$ попарно непересекающихся заражённых отрезков на числовой прямой. $$$i$$$-й отрезок — это $$$[l_i, r_i]$$$: каждая целочисленная позиция $$$x$$$, для которой $$$l_i \le x \le r_i$$$, заражена. Все целочисленные позиции, не покрытые ни одним из отрезков, не заражены.

В ряд стоят $$$m$$$ человек. Если первый человек стоит на позиции $$$s$$$, то люди стоят на позициях $$$s, s + 1, \ldots, s + m - 1$$$. Человек заражён, если позиция, на которой он стоит, заражена.

Для целого числа $$$s$$$ обозначим через $$$f(s)$$$ количество заражённых людей, когда первый человек стоит на позиции $$$s$$$.

Дано целое число $$$k$$$. Найдите любое целое число $$$s$$$, для которого $$$f(s) = k$$$, или определите, что такого $$$s$$$ не существует.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит три целых числа $$$n$$$, $$$m$$$ и $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le m \le 10^9$$$, $$$0 \le k \le m$$$) — количество заражённых отрезков, количество людей и требуемое количество заражённых людей.

$$$i$$$-я из следующих $$$n$$$ строк содержит два целых числа $$$l_i$$$ и $$$r_i$$$ ($$$1 \le l_i \le r_i \le 10^{15}$$$) — концы $$$i$$$-го заражённого отрезка. Гарантируется, что $$$r_i + 1 \lt l_{i + 1}$$$ для каждого $$$i$$$ от $$$1$$$ до $$$n - 1$$$, поэтому отрезки попарно не пересекаются, никакие два из них не являются соседними, и они заданы слева направо.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

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

Для каждого набора входных данных, если не существует целого числа $$$s$$$, для которого $$$f(s) = k$$$, выведите $$$-1$$$.

Иначе выведите одно целое число $$$s$$$ ($$$1 \le s \le 10^{18}$$$) — позицию, для которой $$$f(s) = k$$$. Можно показать, что если хотя бы одна такая позиция существует, то существует и позиция в указанных границах.

Если подходящих позиций несколько, выведите любую из них.

Пример
Входные данные
6
1 5 5
7 11
2 4 3
1 2
5 6
3 5 4
1 3
5 6
8 8
1 3 2
10 12
3 6 0
1 1
4 5
10 12
1 1000000000 1
1000000000000000 1000000000000000
Выходные данные
7
-1
2
9
42
999999876543210
Примечание

В первом примере одна из подходящих позиций — $$$s = 7$$$. Тогда люди стоят на позициях $$$7, 8, 9, 10, 11$$$, каждая из которых заражена, поэтому $$$f(7) = 5$$$.

Во втором примере можно показать, что подходящей позиции не существует.

В третьем примере одна из подходящих позиций — $$$s = 2$$$. Тогда люди стоят на позициях $$$2, 3, 4, 5, 6$$$. Позиции $$$2$$$, $$$3$$$, $$$5$$$ и $$$6$$$ заражены, а позиция $$$4$$$ — нет, поэтому $$$f(2) = 4$$$.