D. Пересечения отрезков
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам заданы два списка отрезков $$$[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$$$.

Пример
Входные данные
3
3 5
1 2
3 4
2 1000000000
1 1
999999999 999999999
10 3
5 10
7 8
Выходные данные
7
2000000000
0
Примечание

В первом наборе входных данных, мы можем достигнуть суммарного пересечения $$$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$$$.

Во втором наборе, мы можем сделать $$$[al_1, ar_1] = [0, 1000000000]$$$ за $$$1000000000$$$ шагов и $$$[bl_1, br_1] = [0, 1000000000]$$$ за $$$1000000000$$$ шагов.

В третьем наборе, суммарное пересечение $$$I$$$ уже равно $$$10 > 3$$$, а потому, не нужно делать ни одного шага.