Server Maintenance Scheduling

You are given a set of servers where each server is represented by three parameters: the start time s, the maintenance duration m, and the recovery time r. When maintaining a server, you cannot start before its specified start time, and once the maintenance is complete, you must add its recovery time.

The task is to determine the minimum total time required to complete the maintenance of all servers for each test case. Formally, if you process the servers in increasing order of their start times, let the current time be updated as follows:

\[ \text{current_time} = \max(\text{current_time}, s_i) + m_i \]

and the answer for that test case is given by:

\[ \text{answer} = \max_{i}(\text{current_time} + r_i) \]

Design an algorithm that schedules the server maintenance so that the final recovery time is minimized.

inputFormat

The input is read from stdin and has the following format:

T
N_1
s_1 m_1 r_1
... (N_1 lines for test case 1)
N_2
s_1 m_1 r_1
... (N_2 lines for test case 2)
...
N_T
s_1 m_1 r_1
... (N_T lines for test case T)

where:

• T is the number of test cases,
• For each test case, N is the number of servers, followed by N lines each containing three integers representing the start time s, maintenance time m, and recovery time r.

outputFormat

For each test case, output the minimum total time required (i.e., the time at which all servers have recovered) on a separate line to stdout.

## sample

2
2
0 3 2
5 4 1
3
2 6 3
1 5 2
4 2 3

10
17