CF2189B The Curse of the Frog

在一条无限的数轴上，青蛙起始于 $0$ 号点。经过多年的冥想修炼，青蛙掌握了 $n$ 种独特的魔法跳跃方式。第 $i$ 种跳跃方式可以让它向前跳不超过 $a_i$ 个单位。换句话说，如果它当前在整数点 $k$，那么跳跃后可以落在从 $k$ 到 $k+a_i$ 的任意一个整数点上。 但魔法总是要付出代价的；青蛙被施加了诅咒。在每次第 $b_i$ 次尝试（即第 $b_i$ 次、第 $2b_i$ 次、第 $3b_i$ 次等）使用第 $i$ 种跳跃方式之前，它会被迫后退 $c_i$ 个单位！也就是说，若它在点 $k$，则会先到达 $k-c_i$，之后才能跳到 $k-c_i$ 到 $k-c_i+a_i$ 间的任意整数点。 青蛙的目标是通过跳跃最小化遭遇回退的次数，最终到达 $x$ 号点。请你帮助青蛙 —— 求出它到达目标点至少需要经历多少次回退，若无法到达 $x$ 点，则输出 $-1$。

每组测试数据包含多个测试用例。第一行包含测试用例个数 $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$ 点，输出最少需要经历的回退次数；若无法到达，则输出 $-1$。

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