CF2189B The Curse of the Frog

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

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

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

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