Bus#3924
Vasilyich is a bus driver, and he has a really tough job, because he has to transfer passengers from point to point 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 segments, 1 \le N \le 1000, which he passes sequentially, starting from the beginning of first and finishing up at the end of -th segment. Every segment has a length D_i kilometers, 1 \le D_i \le 1000.
Of course, there are speed limits on Vasilyich's route. Every segment has its own speed limit L_i, 1 \le L_i \le 100000 km/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 \le H_i \le 1000. A driver can be stopped at most once in a segment.
Bus is travelling along the route with a constant speed that Vasilyich chooses at the beginning (point ). Maximum speed that the bus can achieve is , 1 \le M \le 100000 km/h. Please help Vasilyich to choose the right speed in order to reach destination as quickly as possible.
The first line of the input contains an integer number – the number of test cases. Then test cases follow, T \le 100.
Each test case starts with a line containing numbers, separated by space: the number of segments on Vasilyich's route and maximum bus speed . Each -th line of the following lines, contains space-separated variables D_i, L_i and H_i for -th segment.
For every test case you should print speed on a separate line. If the answer is ambiguous, choose the highest value.
Esempio 1