← 返回题目列表

Codeforces · 1389/D

D. 线段交叉点

中文机器翻译题面 查看原题

给定两个段列表 $$$[al_1, ar_1], [al_2, ar_2], \dots, [al_n, ar_n]$$$ 和 $$$[bl_1, br_1], [bl_2, br_2], \dots, [bl_n, br_n]$$$。

最初,所有段 $$$[al_i, ar_i]$$$ 等于 $$$[l_1, r_1]$$$,所有段 $$$[bl_i, br_i]$$$ 等于 $$$[l_2, r_2]$$$。

在一个步骤中,您可以选择一个段(从第一个列表或第二个列表中)并将其扩展 $$$1$$$。换句话说,假设您选择了段 $$$[x, y]$$$,那么您可以将其转换为 $$$[x - 1, y]$$$ 或 $$$[x, y + 1]$$$。

让我们将总交集 $$$I$$$ 定义为相应线段对的交集长度之和,即 $$$\sum\limits_{i=1}^{n}{\text{intersection_length}([al_i, ar_i], [bl_i, br_i])}$$$。空交集的长度为 $$$0$$$,线段 $$$[x, y]$$$ 的长度等于 $$$y - x$$$。

使$$$I$$$ 大于或等于$$$k$$$ 需要最少多少步?

输入

第一行包含单个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$; $$$1 \le k \le 10^9$$$) - 列表的长度和所需的最小总交集。

每个测试用例的第二行包含两个整数 $$$l_1$$$ 和 $$$r_1$$$ ($$$1 \le l_1 \le r_1 \le 10^9$$$) - 所有 $$$[al_i, ar_i]$$$ 最初等于的段。

每个测试用例的第三行包含两个整数 $$$l_2$$$ 和 $$$r_2$$$ ($$$1 \le l_2 \le r_2 \le 10^9$$$) - 所有 $$$[bl_i, br_i]$$$ 最初等于的段。

保证 $$$n$$$ 的总和不超过 $$$2 \cdot 10^5$$$。

输出

打印 $$$t$$$ 整数 - 每个测试用例一个。对于每个测试用例,打印使 $$$I$$$ 大于或等于 $$$k$$$ 所需的最小步骤数。

示例

输入 #1

3
3 5
1 2
3 4
2 1000000000
1 1
999999999 999999999
10 3
5 10
7 8

输出 #1

7
2000000000
0

注意

在第一个测试用例中,我们可以实现总交集$$$5$$$,例如,使用下一个策略:

- 以$$$2$$$步骤从$$$[1, 2]$$$到$$$[1, 4]$$$;
- 在 $$$1$$$ 步骤中将 $$$[al_2, ar_2]$$$ 从 $$$[1, 2]$$$ 变为 $$$[1, 3]$$$;
- 以$$$2$$$步骤从$$$[3, 4]$$$到$$$[1, 4]$$$;
- 以$$$2$$$步骤从$$$[3, 4]$$$到$$$[1, 4]$$$。

在第二个测试用例中,我们可以在 $$$1000000000$$$ 步骤中创建 $$$[al_1, ar_1] = [0, 1000000000]$$$,在 $$$[bl_1, br_1] = [0, 1000000000]$$$ 中$$$1000000000$$$ 步。

在第三个测试用例中,总交集 $$$I$$$ 已经等于 $$$10 > 3$$$,因此我们不需要执行任何步骤。