CF1389D.Segment Intersections

You are given two lists of segments $[al_1, ar_1], [al_2, ar_2], \dots, [al_n, ar_n]$ and $[bl_1, br_1], [bl_2, br_2], \dots, [bl_n, br_n]$.

Initially, all segments $[al_i, ar_i]$ are equal to $[l_1, r_1]$ and all segments $[bl_i, br_i]$ are equal to $[l_2, r_2]$.

In one step, you can choose one segment (either from the first or from the second list) and extend it by $1$. In other words, suppose you've chosen segment $[x, y]$ then you can transform it either into $[x - 1, y]$ or into $[x, y + 1]$.

Let's define a total intersection $I$ as the sum of lengths of intersections of the corresponding pairs of segments, i.e. \sum\limits_{i=1}^{n}{\text{intersection_length}([al_i, ar_i], [bl_i, br_i])}. Empty intersection has length $0$ and length of a segment $[x, y]$ is equal to $y - x$.

What is the minimum number of steps you need to make $I$ greater or equal to $k$?

给你两组线段：$[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 \ge k$ 所需的最少操作步数是多少？

The first line contains the single integer $t$ ($1 \le t \le 1000$) — 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 length of lists and the minimum required total intersection.

The second line of each test case contains two integers $l_1$ and $r_1$ ($1 \le l_1 \le r_1 \le 10^9$) — the segment all $[al_i, ar_i]$ are equal to initially.

The third line of each test case contains two integers $l_2$ and $r_2$ ($1 \le l_2 \le r_2 \le 10^9$) — the segment all $[bl_i, br_i]$ are equal to initially.

It's guaranteed that the sum of $n$ doesn't exceed $2 \cdot 10^5$.

第一行包含一个整数 $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$。

Print $t$ integers — one per test case. For each test case, print the minimum number of step you need to make $I$ greater or equal to $k$.

输出 $t$ 个整数——每个测试用例输出一个整数。对于每个测试用例，输出使 $I$ 大于或等于 $k$ 所需的最少步数。

In the first test case, we can achieve total intersection $5$, for example, using next strategy:

• make $[al_1, ar_1]$ from $[1, 2]$ to $[1, 4]$ in $2$ steps;
• make $[al_2, ar_2]$ from $[1, 2]$ to $[1, 3]$ in $1$ step;
• make $[bl_1, br_1]$ from $[3, 4]$ to $[1, 4]$ in $2$ steps;
• make $[bl_2, br_2]$ from $[3, 4]$ to $[1, 4]$ in $2$ steps.

In result, I = \text{intersection_length}([al_1, ar_1], [bl_1, br_1]) + \text{intersection_length}([al_2, ar_2], [bl_2, br_2]) + \\ + \text{intersection_length}([al_3, ar_3], [bl_3, br_3]) = 3 + 2 + 0 = 5

In the second test case, we can make $[al_1, ar_1] = [0, 1000000000]$ in $1000000000$ steps and $[bl_1, br_1] = [0, 1000000000]$ in $1000000000$ steps.

In the third test case, the total intersection $I$ is already equal to $10 \gt 3$, so we don't need to do any steps.

在第一个测试用例中，我们可以通过以下策略实现总交集长度为 $5$：

• 将 $[al_1, ar_1]$ 从 $[1, 2]$ 扩展为 $[1, 4]$，耗时 $2$ 步；
• 将 $[al_2, ar_2]$ 从 $[1, 2]$ 扩展为 $[1, 3]$，耗时 $1$ 步；
• 将 $[bl_1, br_1]$ 从 $[3, 4]$ 扩展为 $[1, 4]$，耗时 $2$ 步；
• 将 $[bl_2, br_2]$ 从 $[3, 4]$ 扩展为 $[1, 4]$，耗时 $2$ 步。

最终，

$$I = \text{intersection\_length}([al_1, ar_1], [bl_1, br_1]) + \text{intersection\_length}([al_2, ar_2], [bl_2, br_2]) + \\ + \text{intersection\_length}([al_3, ar_3], [bl_3, br_3]) = 3 + 2 + 0 = 5$$

在第二个测试用例中，我们可以在 $1000000000$ 步内将 $[al_1, ar_1]$ 变为 $[0, 1000000000]$，并在 $1000000000$ 步内将 $[bl_1, br_1]$ 变为 $[0, 1000000000]$。

在第三个测试用例中，总交集长度 $I$ 已为 $10 > 3$，因此无需执行任何操作。