给定两个段列表 $$$[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$$$,因此我们不需要执行任何步骤。