CF1821D Black Cells

你正在玩一个游戏，游戏中有一条非常长的带子，由 $10^{18}$ 个白色格子组成，从左到右编号为 $0$、$1$、$2$，依此类推。你控制着一个特殊的指针，初始时指针在第 $0$ 个格子上。同时，你有一个“Shift”按钮可以按下并保持。 每一步操作，你可以进行以下三种操作之一： - 将指针向右移动（从格子 $x$ 移动到格子 $x+1$）； - 按下并保持“Shift”按钮； - 松开“Shift”按钮：在你松开“Shift”按钮的那一刻，所有在按住“Shift”期间访问过的格子都会被染成黑色。 （当然，如果已经按住了 Shift，就不能再次按下。同理，如果没有按下 Shift，也不能松开。） 你的目标是将至少 $k$ 个格子染成黑色，但有一个限制：你被给定了 $n$ 个区间 $[l_i, r_i]$ ——你只能在这些区间内染色，也就是说，只有当 $l_i \le x \le r_i$ 对某个 $i$ 成立时，才能将格子 $x$ 染色。 你需要计算，为了将至少 $k$ 个格子染成黑色，最少需要多少步操作。

第一行包含一个整数 $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 < l_2 < \dots < 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 < l_{i+1} - 1$），其中 $r_i$ 表示第 $i$ 个区间的右端点。 输入的额外约束： - 每个格子最多属于一个区间； - 所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

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

在第一个测试用例中，一种最优的操作序列如下： 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$ 个格子。 由 ChatGPT 4.1 翻译