# This content is archived!

For the 2018-2019 school year, we have switched to using the WLMOJ judge for all MCPT related content. This is an archive of our old website and will not be updated.

# Problem

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

The first line of the input provides the number of test cases, $T (1 \leq T \leq 100)$. $T$ test cases follow. Each test case begins with two integers $N (1 \leq N \leq 10^7)$ and $M (1 \leq M \leq 10^4)$. M lines follow, each containing three integers $A$, $L$, and $B$. $(1 \leq A, L \leq 10^7, 1 \leq B \leq 1000)$

# Output

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.

# Explanation for Sample Output

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^\text{th}$ second.

# Editorial

Read only if you are stuck or have already solved the problem.