A16470 · 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

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

输出 #1

0
1
-1
2
298892990032
3