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

K1o0n вызвался поработать ассистентом на кафедре физики, и ему досталось $$$n$$$ учебных лабораторий. В $$$i$$$-й лаборатории стоят три прибора; их показания равны $$$a_i$$$, $$$b_i$$$ и $$$c_i$$$. Приборы различимы, и порядок в этой тройке закреплён: первый ($$$a_i$$$), второй ($$$b_i$$$), третий ($$$c_i$$$).

Одно действие — это выбрать номер лаборатории $$$i$$$ и выполнить ровно одну из трёх поправок:

  • $$$c_i \mathrel{+}= \operatorname{sgn}(a_i - b_i)$$$
  • $$$b_i \mathrel{+}= \operatorname{sgn}(a_i - c_i)$$$
  • $$$a_i \mathrel{+}= \operatorname{sgn}(b_i - c_i)$$$

Здесь $$$\operatorname{sgn}(x)$$$ равен $$$1$$$ при $$$x \gt 0$$$, равен $$$-1$$$ при $$$x \lt 0$$$ и равен $$$0$$$ при $$$x = 0$$$.

Иначе говоря, поправка сдвигает на единицу показание одного прибора, а направление сдвига задаёт разность показаний двух остальных, взятых в порядке записи: раньше стоящий минус позже стоящий.

Действия выполняются по очереди, и каждая поправка смотрит на показания, сложившиеся к этому моменту. Одну и ту же лабораторию можно править сколько угодно раз, а какие-то не трогать вовсе; всего K1o0n готов сделать не более $$$k$$$ действий суммарно по всем лабораториям.

Работу оценят по самой запущенной лаборатории:

$$$$$$S = \min_{1 \le i \le n} (a_i + b_i + c_i),$$$$$$

где показания берутся после всех действий. K1o0n хочет впечатлить коллег, поэтому просит найти наибольшее $$$S$$$, которого он может добиться.

Входные данные

Первая строка содержит целое число $$$t$$$ ($$$1 \le t \le 10^4$$$)  — количество наборов входных данных.

Первая строка каждого набора содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$0 \le k \le 10^{18}$$$) — количество лабораторий и максимальное количество действий.

Следующие $$$n$$$ строк каждого набора содержат три целых числа $$$a_i$$$, $$$b_i$$$ и $$$c_i$$$ ($$$-10^9 \le a_i, b_i, c_i \le 10^9$$$).

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2\cdot10^5$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число — наибольшее достижимое значение $$$S$$$.

Обратите внимание, что ответ может не поместиться в 32-битный тип данных. Используйте 64-битный тип (long long в C++, long в Java).

Пример
Входные данные
5
3 4
-3 -1 -2
1 3 5
2 4 6
3 4
6 4 2
6 7 0
7 6 0
3 1000000000000000000
4 4 4
1 5 9
-1000000000 0 1000000000
2 4
1 2 3
0 0 5
4 3
2 1 0
4 4 5
1 5 9
7 -2 1
Выходные данные
-2
14
12
6
6
Примечание

В первом наборе входных данных, чтобы получить минимальную сумму по всем тройкам, равную $$$-2$$$, нужно четыре раза к $$$a_1$$$ прибавить $$$\operatorname{sgn}(b_1 - c_1) = 1$$$. После этого тройка $$$(a_1, b_1, c_1)$$$ станет равна $$$(1, -1, -2)$$$, а сумма в остальных тройках изначально была больше $$$-2$$$. Можно показать, что за столько операций сумму $$$-1$$$ или выше получить невозможно.

Во втором наборе входных данных, чтобы получить минимальную сумму по всем тройкам, равную $$$14$$$, необходимо $$$2$$$ раза к $$$a_1$$$ прибавить $$$\operatorname{sgn}(b_1 - c_1) = 1$$$, один раз к $$$b_2$$$ прибавить $$$\operatorname{sgn}(a_2 - c_2) = 1$$$ и к $$$c_3$$$ прибавить $$$\operatorname{sgn}(a_3 - b_3) = 1$$$.

В четвертом наборе входных данных на первый взгляд нельзя увеличить значение второй лаборатории, однако это не так. Сделаем $$$b_2 \mathrel{+}= \operatorname{sgn}(a_2 - c_2)$$$, и мы выйдем из «застойного» положения.