B. Проклятие лягушки
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На бесконечной числовой прямой в точке $$$0$$$ сидит лягушка. За долгие годы медитации лягушка освоила $$$n$$$ уникальных видов магических прыжков. $$$i$$$-й тип прыжка позволяет ей прыгнуть на не более чем $$$a_i$$$ делений вперед. Иными словами, если она была в целочисленной точке $$$k$$$, то после прыжка может оказаться в любой целой точке от $$$k$$$ до $$$k+a_i$$$.

Но у магии всегда есть цена, на нее наложили проклятие. Перед каждой $$$b_i$$$-й попыткой (перед $$$b_i$$$-й, $$$2b_i$$$-й, $$$3b_i$$$-й и так далее попытками среди прыжков типа $$$i$$$) использования $$$i$$$-го вида прыжка лягушка откатывается на $$$c_i$$$ делений назад! Иными словами, если она была в точке $$$k$$$, то с начала она окажется в точке $$$k-c_i$$$, а после прыжка может оказаться в любой целочисленной точке от $$$k-c_i$$$ до $$$k-c_i+a_i$$$.

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

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

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

В первой строке каждого набора входных данных даны $$$2$$$ целых числа $$$n$$$ и $$$x$$$ ($$$1 \leq n \leq 10^5$$$, $$$1 \leq x \leq 10^{18}$$$) — количество видов прыжков лягушки и её конечная цель.

В следующих $$$n$$$ строках находится описание видов прыжков, $$$i$$$-я строка содержит $$$3$$$ целых числа $$$a_i$$$, $$$b_i$$$ и $$$c_i$$$ ($$$1 \leq a_i, b_i, c_i \leq 10^6$$$).

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

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

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

Пример
Входные данные
6
1 1
3 3 3
1 7
4 2 5
2 4
1 2 3
2 2 4
5 8
12 1 11
10 1 4
1 1 3
1 2 5
2 1 7
1 1000000000000000000
1000000 4 654321
1 10
2 2 1
Выходные данные
0
1
-1
2
298892990032
3
Примечание

В первом наборе входных данных лягушка может прыгнуть на $$$1$$$ деление вперед и окажется в точке $$$1$$$. Таким образом, ответ $$$0$$$.

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

В четвертом наборе входных данных лягушка может добраться до точки $$$8$$$, например, следующим образом: прыгнуть прыжком $$$1$$$-го типа на $$$12$$$, прыгнуть прыжком $$$4$$$-го типа на $$$1$$$ и прыгнуть прыжком $$$2$$$-го типа на $$$10$$$. Тогда она последовательно окажется в следующих точках $$$0 \rightarrow \text{(откат)} -11 \rightarrow 1 \rightarrow 2 \rightarrow \text{(откат)} -2 \rightarrow 8$$$.

В шестом наборе входных данных лягушка может добраться до точки $$$10$$$, например, следующим образом: $$$6$$$ раз прыгнуть на $$$2$$$ и $$$1$$$ раз на $$$1$$$. Тогда она последовательно окажется в следующих точках $$$0 \rightarrow 2 \rightarrow \text{(откат)} 1 \rightarrow 3 \rightarrow 5 \rightarrow \text{(откат)} 4 \rightarrow 6 \rightarrow 8 \rightarrow \text{(откат)} 7 \rightarrow 9 \rightarrow 10$$$.