Segment Intersections
Contest: Educational Codeforces Round 92 (Rated for Div. 2)
Difficulty rating: 2100
Tags: brute force, greedy, implementation, math

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

Input format:
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$$$.

Output format:
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$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
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 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.

Example input:
3
3 5
1 2
3 4
2 1000000000
1 1
999999999 999999999
10 3
5 10
7 8

Example output:
7
2000000000
0

Editorial:
At first, note that intersection_length of segments $$$[l_1, r_1]$$$ and $$$[l_2, r_2]$$$ can be calculated as $$$\min(r_1, r_2) - \max(l_1, l_2)$$$. If it's negative then segments don't intersect, otherwise it's exactly length of intersection.
Now we have two major cases: do segments $$$[l_1, r_1]$$$ and $$$[l_2, r_2]$$$ already intersect or not.
If segments intersect then we already have $$$n \cdot (\min(r_1, r_2) - \max(l_1, l_2))$$$ as the total intersection. Note, that making both segments equal to $$$[\min(l_1, l_2), \max(r_1, r_2)]$$$ in each pair are always optimal since in each step we will increase the total intersection by $$$1$$$.
After making all segments equal to $$$[\min(l_1, l_2), \max(r_1, r_2)]$$$ we can increase total intersection by $$$1$$$ only in two steps: we need to extend both segments in one pair.
In result, we can find not a hard formula to calculate the minimum number of steps: we already have $$$n \cdot (\min(r_1, r_2) - \max(l_1, l_2))$$$ of the total intersection, then we can increase it by at most $$$n \cdot ((\max(r_1, r_2) - \min(l_1, l_2)) - (\min(r_1, r_2) - \max(l_1, l_2)))$$$ using one step per increase, and then to any number using two steps per increase.
In the case of non-intersecting $$$[l_1, l_2]$$$ and $$$[r_1, r_2]$$$, we should at first "invest" some number of steps in each pair to make them intersect. So let's iterate over the number of segments to "invest" $$$cntInv$$$. We should make $$$cntInv \cdot (\max(l_1, l_2) - \min(r_1, r_2))$$$ steps to make segments touch. Now, $$$cntInv$$$ segments touch so we can use almost the same formulas for them as in the previous case.
The total complexity is $$$O(n)$$$ per test case.