← 返回题目列表

Codeforces · 2189/B

B. 青蛙的诅咒

中文机器翻译题面 查看原题

在无限数轴上,$$$0$$$ 处,坐着一只青蛙。经过多年的冥想,青蛙已经掌握了 $$$n$$$ 独特的魔法跳跃类型。第 $$$i$$$ 类型的跳转允许其向前跳转不超过 $$$a_i$$$ 单位。换句话说,如果它在整数点$$$k$$$,则跳转后它可以着陆 从 $$$k$$$ 到 $$$k+a_i$$$ 的任意整数点.

但魔法总是有代价的;它已经被诅咒了。在每次尝试使用第 $$$i$$$ 类型的跳跃之前(在第 $$$b_i$$$-th、$$$2b_i$$$-th、$$$3b_i$$$-th 等尝试在 $$$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$$$-st类型跳转$$$12$$$,使用$$$4$$$-th类型跳转$$$1$$$,使用$$$2$$$-nd类型跳转$$$10$$$。然后它将依次位于以下点 $$$0 \rightarrow \text{(rollback)} -11 \rightarrow 1 \rightarrow 2 \rightarrow \text{(rollback)} -2 \rightarrow 8$$$。

在第六个测试用例中,青蛙可以到达点$$$10$$$,例如,如下:跳$$$6$$$次$$$2$$$,跳$$$1$$$次$$$1$$$。然后它将依次位于以下点 $$$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$$$。