On New Year's Eve, the city of Toronto hosts a fireworks show. The show lasts seconds, over the course of which fireworks are used. Each firework goes off at a certain time , hangs in the air for seconds, and has a brightness of . That means that between time and (inclusive), the brightness of the sky increases by .
Given , and for each firework, figure out at which point in time is the sky the brightest.
The first line of the input provides the number of test cases, . test cases follow. Each test case begins with two integers and . lines follow, each containing three integers , , and
For each test case, your program should output one integer: the time at which the sky is the brightest. If there are multiple points in time at which the sky is brightest, output the time of the last one.
2 5 3 1 1 3 2 4 1 3 2 1 10 3 1 4 3 4 4 4 7 4 5
Explanation of Sample
In the second test case, the brightness of the sky, starting at second, is , so the sky is brightest in the second.