## 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 $$N$$ seconds, over the course of which $$M$$ fireworks are used. Each firework goes off at a certain time $$A$$, hangs in the air for $$L$$ seconds, and has a brightness of $$B$$. That means that between time $$A$$ and $$A+L-1$$ (inclusive), the brightness of the sky increases by $$B$$.

Given $$A, L$$, and $$B$$ 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, $$T\ (1 \le T \le 100)$$. $$T$$ test cases follow. Each test case begins with two integers $$N\ (1 \le N \le 10^7)$$ and $$M\ (1 \le M \le 10^4)$$. $$M$$ lines follow, each containing three integers $$A$$, $$L$$, and $$B\ (1 \le A, L \le 10^7, 1 \le B \le 1\ 000)$$

#### 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 $$t = 1$$ second, is $$[3, 3, 3, 7, 4, 4, 9, 5, 5, 5]$$, so the sky is brightest in the $$7^{th}$$ second.