Segment Intersections

题意翻译

有两组线段，每组有 $n$ 条，分别表示为 $\left[a l_{1}, a r_{1}\right],\left[a l_{2}, a r_{2}\right], \ldots,\left[a l_{n}, a r_{n}\right]$ 和 $\left[b l_{1}, b r_{1}\right],\left[b l_{2}, b r_{2}\right], \ldots,\left[b l_{n}, b r_{n}\right]$。 一开始所有第一组内的线段都等于 $\left[l_{1}, r_{1}\right]$，第二组内的线段都等于 $\left[l_{2}, r_{2}\right]$。 每次操作可以选择一条线段并将其扩展 $1$ 单位长度。具体来说，你可以选择一条线段 $[x, y]$ 并将其转化为 $[x-1, y]$ 或 $[x, y+1]$。 定义 $\left[a l_{i}, a r_{i}\right]$ 和 $\left[b l_{i}, b r_{i}\right]$ 为一组**对应线段**。定义 $I$ 为每组对应线段的**交**的长度之和。线段 $[x,y]$ 的长度定义为 $y-x$。 求使 $I$ 达到（大于等于） $k$ 所需的最少操作数。 $1 \le n \le 10^5$，$1 \le k \le 10^9$

题目描述

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 $ ?

输入输出格式

输入格式

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 $ .

输出格式

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 $ .

输入输出样例

输入样例 #1

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

输出样例 #1

7
2000000000
0

说明

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 > 3 $ , so we don't need to do any steps.