CF1821D.Black Cells

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.

(Of course, you can't press Shift if you already hold it. Similarly, you can't release Shift if you haven't pressed it.)

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?

你正在操作一条非常长的纸带，上面有 $10^{18}$ 个白色格子，从左到右依次编号为 $0$、$1$、$2$，依此类推。你控制一个特殊的指针，初始时位于第 $0$ 号格子。此外，你还有一个可按住的“Shift”键。

每一步操作中，你可以执行以下三种动作之一：

• 将指针向右移动（从格子 $x$ 移动到格子 $x + 1$）；
• 按下并按住“Shift”键；
• 松开“Shift”键：在松开“Shift”的瞬间，所有在“Shift”被按下期间访问过的格子将被染成黑色。

（当然，若当前已按住“Shift”，则不能再按；同理，若尚未按下“Shift”，则不能松开。）

你的目标是至少将 $k$ 个格子染成黑色，但存在一个限制条件：题目给出 $n$ 个区间 $[l_i, r_i]$，你只能在这些区间内部染色，即：仅当存在某个 $i$ 使得 $l_i \le x \le r_i$ 时，才允许将格子 $x$ 染黑。

为达成目标，最少需要多少步操作？

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 \lt l_2 \lt \dots \lt 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 \lt 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$.

第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 表示测试用例的数量。

每个测试用例的第一行包含两个整数 $n$ 和 $k$（$1 \le n \le 2 \cdot 10^5$；$1 \le k \le 10^9$）—— 分别表示线段的数量和目标黑色格子数量。

每个测试用例的第二行包含 $n$ 个整数 $l_1, l_2, \dots, l_n$（$1 \le l_1 \lt l_2 \lt \dots \lt l_n \le 10^9$），其中 $l_i$ 表示第 $i$ 条线段的左端点。

每个测试用例的第三行包含 $n$ 个整数 $r_1, r_2, \dots, r_n$（$1 \le r_i \le 10^9$；$l_i \le r_i \lt l_{i + 1} - 1$），其中 $r_i$ 表示第 $i$ 条线段的右端点。

输入的额外约束条件：

• 每个格子至多属于一条线段；
• 所有测试用例中 $n$ 的总和不超过 $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.

对于每个测试用例，输出将至少 $k$ 个格子染成黑色所需的最少操作次数；如果无法实现，则输出 $-1$。

In the first test case, one of the optimal sequences of operations is the following:

1. Move right: pointer is moving into cell $1$;
2. Press Shift;
3. Release Shift: cell $1$ is colored black;
4. Move right: pointer is moving into cell $2$;
5. Move right: pointer is moving into cell $3$;
6. Press Shift;
7. Move right: pointer is moving into cell $4$;
8. Release Shift: cells $3$ and $4$ are colored in black.

We've colored $3$ cells in $8$ moves.

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:

1. Move right: pointer is moving into cell $1$;
2. Move right: pointer is moving into cell $2$;
3. Move right: pointer is moving into cell $3$;
4. Press Shift;
5. Move right: pointer is moving into cell $4$;
6. Move right: pointer is moving into cell $5$;
7. Release Shift: cells $3$, $4$ and $5$ are colored in black.

We've colored $3$ cells in $7$ moves.

在第一个测试用例中，一种最优的操作序列如下：

1. 向右移动：指针移入第 $1$ 个单元格；
2. 按下 Shift 键；
3. 松开 Shift 键：第 $1$ 个单元格被涂黑；
4. 向右移动：指针移入第 $2$ 个单元格；
5. 向右移动：指针移入第 $3$ 个单元格；
6. 按下 Shift 键；
7. 向右移动：指针移入第 $4$ 个单元格；
8. 松开 Shift 键：第 $3$ 和第 $4$ 个单元格被涂黑。

我们共用 $8$ 步操作涂黑了 $3$ 个单元格。

在第二个测试用例中，最多只能涂黑 $8$ 个单元格，而我们需要涂黑 $20$ 个单元格。

在第三个测试用例中，一种最优的操作序列如下：

1. 向右移动：指针移入第 $1$ 个单元格；
2. 向右移动：指针移入第 $2$ 个单元格；
3. 向右移动：指针移入第 $3$ 个单元格；
4. 按下 Shift 键；
5. 向右移动：指针移入第 $4$ 个单元格；
6. 向右移动：指针移入第 $5$ 个单元格；
7. 松开 Shift 键：第 $3$、$4$ 和 $5$ 个单元格被涂黑。

我们共用 $7$ 步操作涂黑了 $3$ 个单元格。