Black Cells
Description
You are playing with a really long strip consisting of $10^{18}$ white cells, numbered from left to right as $0$, $1$, $2$ and so on. You are controlling a special pointer that is initially in cell $0$. Also, you have a "Shift" button you can press and hold.
In one move, you can do one of three actions:
- move the pointer to the right (from cell $x$ to cell $x + 1$);
- press and hold the "Shift" button;
- release the "Shift" button: the moment you release "Shift", all cells that were visited while "Shift" was pressed are colored in black.
Your goal is to color at least $k$ cells, but there is a restriction: you are given $n$ segments $[l_i, r_i]$ — you can color cells only inside these segments, i. e. you can color the cell $x$ if and only if $l_i \le x \le r_i$ for some $i$.
What is the minimum number of moves you need to make in order to color at least $k$ cells black?
The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
The first line of each test case contains two integers $n$ and $k$ ($1 \le n \le 2 \cdot 10^5$; $1 \le k \le 10^9$) — the number of segments and the desired number of black cells, respectively.
The second line contains $n$ integers $l_1, l_2, \dots, l_n$ ($1 \le l_1 < l_2 < \dots < l_n \le 10^9$), where $l_i$ is the left border of the $i$-th segment.
The third line contains $n$ integers $r_1, r_2, \dots, r_n$ ($1 \le r_i \le 10^9$; $l_i \le r_i < l_{i + 1} - 1$), where $r_i$ is the right border of the $i$-th segment.
Additional constraints on the input:
- every cell belongs to at most one segment;
- the sum of $n$ doesn't exceed $2 \cdot 10^5$.
For each test case, print the minimum number of moves to color at least $k$ cells black, or $-1$ if it's impossible.
Input
The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
The first line of each test case contains two integers $n$ and $k$ ($1 \le n \le 2 \cdot 10^5$; $1 \le k \le 10^9$) — the number of segments and the desired number of black cells, respectively.
The second line contains $n$ integers $l_1, l_2, \dots, l_n$ ($1 \le l_1 < l_2 < \dots < l_n \le 10^9$), where $l_i$ is the left border of the $i$-th segment.
The third line contains $n$ integers $r_1, r_2, \dots, r_n$ ($1 \le r_i \le 10^9$; $l_i \le r_i < l_{i + 1} - 1$), where $r_i$ is the right border of the $i$-th segment.
Additional constraints on the input:
- every cell belongs to at most one segment;
- the sum of $n$ doesn't exceed $2 \cdot 10^5$.
Output
For each test case, print the minimum number of moves to color at least $k$ cells black, or $-1$ if it's impossible.
4
2 3
1 3
1 4
4 20
10 13 16 19
11 14 17 20
2 3
1 3
1 10
2 4
99 999999999
100 1000000000
8
-1
7
1000000004
Note
In the first test case, one of the optimal sequences of operations is the following:
- Move right: pointer is moving into cell $1$;
- Press Shift;
- Release Shift: cell $1$ is colored black;
- Move right: pointer is moving into cell $2$;
- Move right: pointer is moving into cell $3$;
- Press Shift;
- Move right: pointer is moving into cell $4$;
- Release Shift: cells $3$ and $4$ are colored in black.
In the second test case, we can color at most $8$ cells, while we need $20$ cell to color.
In the third test case, one of the optimal sequences of operations is the following:
- Move right: pointer is moving into cell $1$;
- Move right: pointer is moving into cell $2$;
- Move right: pointer is moving into cell $3$;
- Press Shift;
- Move right: pointer is moving into cell $4$;
- Move right: pointer is moving into cell $5$;
- Release Shift: cells $3$, $4$ and $5$ are colored in black.