您正在玩一条由 $$$10^{18}$$$ 白色单元格组成的长条,从左到右编号为 $$$0$$$、$$$1$$$、$$$2$$$ 等。您正在控制一个最初位于单元格 $$$0$$$ 中的特殊指针。此外,您还有一个可以按住的“Shift”按钮。
在一个动作中,你可以执行以下三个动作之一:
- 将指针向右移动(从单元格 $$$x$$$ 到单元格 $$$x + 1$$$);
- 按住“Shift”按钮;
- 释放“Shift”按钮:释放“Shift”按钮时,按下“Shift”时访问的所有单元格都会显示为黑色。
您的目标是至少为 $$$k$$$ 单元格着色,但有一个限制:您将获得 $$$n$$$ 段 $$$[l_i, r_i]$$$ - 您只能为这些段内的单元格着色,即 e.当且仅当 $$$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
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
输出 #1
8 -1 7 1000000004
注意
在第一个测试用例中,最佳操作顺序之一如下:
1.右移:指针移入单元格$$$1$$$;
2. 按 Shift 键;
3. 释放 Shift:单元格 $$$1$$$ 为黑色;
4.右移:指针移入单元格$$$2$$$;
5.右移:指针移入单元格$$$3$$$;
6. 按 Shift 键;
7. 右移:指针移入单元格$$$4$$$;
8. 释放 Shift:单元格 $$$3$$$ 和 $$$4$$$ 为黑色。
在第二个测试用例中,我们最多可以对 $$$8$$$ 个单元格进行着色,而我们需要 $$$20$$$ 个单元格进行着色。
在第三个测试用例中,最佳操作顺序之一如下:
1.右移:指针移入单元格$$$1$$$;
2.右移:指针移入单元格$$$2$$$;
3.右移:指针移入单元格$$$3$$$;
4. 按 Shift 键;
5.右移:指针移入单元格$$$4$$$;
6.右移:指针移入单元格$$$5$$$;
7. 释放班次:单元格 $$$3$$$、$$$4$$$ 和 $$$5$$$ 为黑色。