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