E. Усердный Бобёр
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Бобр основал строительную компанию «Усердный Бобёр». И теперь, чтобы наработать имидж компании, нужно построить как можно более высокое здание.

У компании есть начальный капитал в $$$x$$$ морковок (очень ценная валюта для бобров) и $$$n$$$ проектов зданий для стройки. Под каждый проект выделена площадка, на которой пока ничего не построено. Проект здания представляет собой последовательность контрактов на постройку очередного этажа. Чтобы построить $$$j$$$-й этаж в $$$i$$$-м здании, нужно потратить $$$a_{i, j}$$$ морковок, за выполнение этого мы моментально получаем $$$b_{i,j}$$$ морковок, которые идут в бюджет, и компания может использовать их для постройки этажей этого же здания выше или для постройки других проектов. Пока что компания молодая, и не все контракты могут быть прибыльными, иначе говоря, возможно, что $$$a_{i,j} \gt b_{i,j}$$$.

Бобр нанял вас, чтобы вы спланировали курс компании. Вы выбираете, в каком порядке строить какие этажи. Обратите внимание, что не обязательно доводить проекты до конца или даже вообще начинать. Более того, между постройкой этажей одного и того же здания можно выполнить произвольное количество контрактов, не относящихся к этому зданию. Главная задача — построить как можно более высокое здание.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 3 \cdot 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

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

Далее следуют $$$n$$$ описаний проектов. В первой строке описания проекта номер $$$i$$$ находится число $$$m_i$$$ — максимальное количество этажей, доступных для постройки в этом здании ($$$1 \le m_i \le 2 \cdot 10^5$$$).

Во второй строке описания проекта вводятся $$$m_i$$$ целых чисел $$$a_{i, 1}, a_{i, 2}, \ldots a_{i, m_i}$$$ — стоимости постройки этажей. В третьей строке вводятся $$$m_i$$$ целых чисел $$$b_{i, 1}, b_{i, 2}, \ldots b_{i, m_i}$$$ — прибыль за постройку этажей. $$$(0 \leq a_{i, j}, b_{i, j} \leq 10^9)$$$.

Гарантируется, что сумма значений $$$m_i$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

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

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

Пример
Входные данные
2
1 6
4
4 4 2 1
2 4 1 1
2 3
2
4 4
5 5
2
2 20
4 0
Выходные данные
4 1
2 1
Примечание

В первом наборе хватает морковок, чтобы последовательно построить все $$$4$$$ этажа единственного здания.

Во втором наборе нужно сначала построить первый этаж второго здания, заработав на этом $$$2$$$ морковки, после этого мы можем построить оба этажа первого здания.