You are given $n$ pairwise disjoint infection intervals on the number line. The $i$-th interval is $[l_i, r_i]$, meaning that every integer position $x$ such that $l_i \le x \le r_i$ is infected. All integer positions not covered by any of the intervals are not infected.

There are $m$ people standing in a row. If the first person stands at position $s$, then the people stand at positions $s, s + 1, \ldots, s + m - 1$. A person is infected if the position they stand at is infected.

For an integer $s$, let $f(s)$ be the number of infected people when the first person stands at position $s$.

You are given an integer $k$. Find any integer $s$ such that $f(s) = k$, or determine that no such $s$ exists.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains three integers $n$, $m$, and $k$ ($1 \le n \le 2 \cdot 10^5$, $1 \le m \le 10^9$, $0 \le k \le m$) — the number of infection intervals, the number of people, and the required number of infected people.

The $i$-th of the following $n$ lines contains two integers $l_i$ and $r_i$ ($1 \le l_i \le r_i \le 10^{15}$) — the endpoints of the $i$-th infection interval. It is guaranteed that $r_i + 1 \lt l_{i + 1}$ for every $i$ from $1$ to $n - 1$, so the intervals are pairwise disjoint, no two of them are adjacent, and they are given from left to right.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

Output

For each test case, if there is no integer $s$ such that $f(s) = k$, output $-1$.

Otherwise, output a single integer $s$ ($1 \le s \le 10^{18}$) — a position such that $f(s) = k$. It can be shown that if at least one such position exists, then a position within these bounds exists as well.

If there are multiple valid positions, output any of them.

Note

In the first example, one valid position is $s = 7$. The people then stand at the positions $7, 8, 9, 10, 11$, all of which are infected, so $f(7) = 5$.

In the second example, it can be shown that there is no suitable position.

In the third example, one valid position is $s = 2$. The people then stand at the positions $2, 3, 4, 5, 6$. Positions $2$, $3$, $5$, and $6$ are infected, while position $4$ is not, so $f(2) = 4$.