CF2189B.The Curse of the Frog

On an infinite number line, at point $0$, sits a frog. After many years of meditation, the frog has mastered $n$ unique types of magical jumps. The $i$-th type of jump allows it to jump forward by no more than $a_i$ units. In other words, if it was at integer point $k$, after the jump it can land at any integer point from $k$ to $k+a_i$.

But magic always comes with a price; it has been cursed. Before each $b_i$-th attempt (before $b_i$-th, $2b_i$-th, $3b_i$-th etc. attempt among the jumps of type $i$) to use the $i$-th type of jump, the frog rolls back $c_i$ units! In other words, if it was at point $k$, it will first find itself at point $k-c_i$, and after the jump, it can land at any integer point from $k-c_i$ to $k-c_i+a_i$.

The frog's goal is to reach the point with the number $x$, using jumps while minimizing the number of rollbacks. Help the frog — find the minimum number of rollbacks it will have to endure on its way to the goal, or determine that it cannot reach point $x$.

在一条无限长的数轴上，一只青蛙位于点 $0$。经过多年的冥想，青蛙掌握了 $n$ 种独特的魔法跳跃方式。第 $i$ 种跳跃方式允许它最多向前跳 $a_i$ 个单位。换言之，若青蛙当前位于整数点 $k$，则跳跃后它可以落在区间 $[k,\, k+a_i]$ 内的任意整数点上。

但魔法总有代价；青蛙因此受到了诅咒。在每次使用第 $i$ 种跳跃方式前，若此次是该类型跳跃的第 $b_i$ 次、第 $2b_i$ 次、第 $3b_i$ 次……尝试（即所有编号为 $b_i$ 的倍数的第 $i$ 类跳跃尝试），青蛙将先向后回退 $c_i$ 个单位！换言之，若青蛙当前位于点 $k$，它会先移动到点 $k-c_i$，然后再执行跳跃，从而可落在区间 $[k-c_i,\, k-c_i+a_i]$ 内的任意整数点上。

青蛙的目标是抵达编号为 $x$ 的点，在使用跳跃的过程中最小化回退次数。请帮助青蛙——求出它抵达目标点所需承受的最少回退次数；若无法抵达点 $x$，则判定为不可达。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

In the first line of each test case, there are $2$ integers $n$ and $x$ ($1 \leq n \leq 10^5$, $1 \leq x \leq 10^{18}$) — the number of types of jumps the frog can make and its final target.

In the following $n$ lines, the description of the jump types is provided; the $i$-th line contains $3$ integers $a_i$, $b_i$, and $c_i$ ($1 \leq a_i, b_i, c_i \leq 10^6$).

It is guaranteed that the sum of $n$ across all test cases does not exceed $10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

在每个测试用例的第一行中，有两个整数 $n$ 和 $x$（$1 \leq n \leq 10^5$，$1 \leq x \leq 10^{18}$）——分别表示青蛙可执行的跳跃类型数量及其最终目标位置。

接下来的 $n$ 行描述了各种跳跃类型；其中第 $i$ 行包含三个整数 $a_i$、$b_i$ 和 $c_i$（$1 \leq a_i, b_i, c_i \leq 10^6$）。

保证所有测试用例的 $n$ 值之和不超过 $10^5$。

For each test case, if the frog can reach point $x$, find the smallest number of rollbacks it must endure to do so. If it cannot reach point $x$, output $-1$.

对于每个测试用例，如果青蛙能够到达点 $x$，请找出它为此必须承受的最小回滚次数；如果无法到达点 $x$，则输出 $-1$。

In the first test case, the frog can jump forward by $1$ unit and will end up at point $1$. Thus, the answer is $0$.

In the third test case, it can be shown that the frog cannot reach point $4$.

In the fourth test case, the frog can reach point $8$, for example, as follows: jump using the $1$-st type by $12$, jump using the $4$-th type by $1$, and jump using the $2$-nd type by $10$. Then it will sequentially be at the following points $0 \rightarrow \text{(rollback)} -11 \rightarrow 1 \rightarrow 2 \rightarrow \text{(rollback)} -2 \rightarrow 8$.

In the sixth test case, the frog can reach point $10$, for example, as follows: jump $6$ times by $2$ and $1$ time by $1$. Then it will sequentially be at the following points $0 \rightarrow 2 \rightarrow \text{(rollback)} 1 \rightarrow 3 \rightarrow 5 \rightarrow \text{(rollback)} 4 \rightarrow 6 \rightarrow 8 \rightarrow \text{(rollback)} 7 \rightarrow 9 \rightarrow 10$.

在第一个测试用例中，青蛙可以向前跳跃 $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$。