TV War

There is only one television in the house, so the family argues every time about which program to watch. You are building a machine that settles the argument automatically.

The programs the family wants to watch during the year are already fixed. Every program starts at the same time each week and ends at the same time each week, so one weekly viewing plan is enough to cover the whole year. Each program has a preference score given by the family, and a higher score means the family wants to watch that program more. Because there is only one television, two programs whose times overlap cannot both be watched.

Choose programs whose viewing times do not overlap so that the total preference is as large as possible, and report that maximum.

The first line contains the number of test cases $t$.

The first line of each test case contains the number of programs $n$ $(1 \le n \le 100000)$. Each of the next $n$ lines contains three integers $s$, $d$, $p$ separated by spaces. $s$ is the time the program starts, $d$ is how long the program lasts, and $p$ is its preference score. $(0 \le s < s+d \le 10080,\ 1 \le p \le 2000)$

If $s+d$ equals $k$, the program ends exactly at time $k$, and another program can be watched starting exactly at time $k$.

For each test case, print the maximum total preference on its own line.

In the first example, taking the program that starts at time $1$ and lasts $4$ together with the program that starts at time $6$ and lasts $4$ gives a total preference of $6+5=11$, which is the largest the family can reach.