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$$$.

Input

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$$$.

Output

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$$$.

Note

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$$$.

The Curse of the Frog

Examples