Bus
Vasilyich is a bus driver, and he has a really tough job, because he has to transfer passengers from point A to pointB safely and as quickly as possible. Moreover, every driver must obey the road rules and regulations, otherwise, he will be fined by local police.
Vasilyich’s route consists of N segments, 1 ≤ N ≤ 1000, which he passes sequentially, starting from the beginning of first and finishing up at the end of N-th segment. Every segment has a length D_i kilometers, 1 ≤ D_i ≤ 1000.
Of course, there are speed limits on Vasilyich’s route. Every segment has its own speed limit L_i, 1 ≤ L_i ≤ 100000km/h. In case the bus driver exceeds it, he is immediately stopped by a police officer, which requires spending H_i hours to fill all the relevant papers. H_i is known beforehand for each segment, 1 ≤ H_i ≤ 1000. A driver can be stopped at most once in a segment.
Bus is travelling along the route with a constant speed S that Vasilyich chooses at the beginning (point A). Time wasted for acceleration and deceleration of the vehicle is negligible, we assume it happens instantly. Maximum speed that the bus can achieve is M, 1 ≤ M ≤ 100000 km/h. Please help Vasilyich to choose the right speed in order to reach destination B as quickly as possible. Passengers like riding fast, so if there are multiple speeds possible choose the highest of them.
Input
First line of the input contains an integer number T – the number of testcases. Then T testcases follow, T ≤ 100.
Each test case starts with a line containing 2 numbers, separated by space: the number of segments N on Vasilyich’s route and maximum bus speed M. Each i-th line of the N following lines, contain space-separated variables D_i, L_i and H_ifor i-th segment.
Output
For every testcase you should print speed S on a separate line.