JDCC '15 Contest 3 P5 - Fireworks

View as PDF

Points: 10
Time limit: 2.0s
Memory limit: 64M

Author:
Problem type

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.

Input Specification

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

Output Specification

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.

Sample Input

2
5 3
1 1 3
2 4 1
3 2 1
10 3
1 4 3
4 4 4
7 4 5

Sample Output

1
7

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.