在无限数轴上,$$$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$$$。
示例
输入复制
61 13 3 31 74 2 52 41 2 32 2 45 812 1 1110 1 41 1 31 2 52 1 71 10000000000000000001000000 4 6543211 102 2 1
输出复制
01-122988929900323
注意
在第一个测试用例中,青蛙可以向前跳跃 $$$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$$$。