310358: CF1821D. Black Cells

D. Black Cellstime limit per test4 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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?

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.

ExampleInput

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

Output

8
-1
7
1000000004

Note

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.

题目大意：给定一个由10^18个白色单元格组成的非常长的条带，从左到右编号为0, 1, 2等。你控制一个特殊的指针，初始位于单元格0中。你还有一个“Shift”按钮可以按下并保持。

在一步中，你可以执行以下三个操作之一：

1. 将指针向右移动（从单元格x移动到单元格x+1）；
2. 按下并保持“Shift”按钮；
3. 释放“Shift”按钮：当你释放“Shift”时，所有在“Shift”按下时访问过的单元格都会被涂成黑色。

目标是将至少k个单元格涂成黑色，但有一个限制：给你n个段[l_i, r_i]，你只能在这些段内涂色，即你只能涂色单元格x，当且仅当对于某个i，l_i <= x <= r_i。

问你需要多少步才能将至少k个单元格涂成黑色？

输入数据格式：

第一行包含一个整数t（1 <= t <= 10^4）——测试用例的数量。

每个测试用例的第一行包含两个整数n和k（1 <= n <= 2 * 10^5；1 <= k <= 10^9）——段的数量和期望的黑色单元格数量。

第二行包含n个整数l_1, l_2, ..., l_n（1 <= l_1 < l_2 < ... < l_n <= 10^9），其中l_i是第i个段的左边界。

第三行包含n个整数r_1, r_2, ..., r_n（1 <= r_i <= 10^9；l_i <= r_i < l_{i+1} - 1），其中r_i是第i个段的右边界。

输出数据格式：

对于每个测试用例，输出将至少k个单元格涂成黑色所需的最小步数，如果不可能，则输出-1。题目大意：给定一个由10^18个白色单元格组成的非常长的条带，从左到右编号为0, 1, 2等。你控制一个特殊的指针，初始位于单元格0中。你还有一个“Shift”按钮可以按下并保持。 在一步中，你可以执行以下三个操作之一： 1. 将指针向右移动（从单元格x移动到单元格x+1）； 2. 按下并保持“Shift”按钮； 3. 释放“Shift”按钮：当你释放“Shift”时，所有在“Shift”按下时访问过的单元格都会被涂成黑色。 目标是将至少k个单元格涂成黑色，但有一个限制：给你n个段[l_i, r_i]，你只能在这些段内涂色，即你只能涂色单元格x，当且仅当对于某个i，l_i <= x <= r_i。 问你需要多少步才能将至少k个单元格涂成黑色？ 输入数据格式： 第一行包含一个整数t（1 <= t <= 10^4）——测试用例的数量。 每个测试用例的第一行包含两个整数n和k（1 <= n <= 2 * 10^5；1 <= k <= 10^9）——段的数量和期望的黑色单元格数量。 第二行包含n个整数l_1, l_2, ..., l_n（1 <= l_1 < l_2 < ... < l_n <= 10^9），其中l_i是第i个段的左边界。 第三行包含n个整数r_1, r_2, ..., r_n（1 <= r_i <= 10^9；l_i <= r_i < l_{i+1} - 1），其中r_i是第i个段的右边界。 输出数据格式： 对于每个测试用例，输出将至少k个单元格涂成黑色所需的最小步数，如果不可能，则输出-1。