Problem Description

There are $N$ airplanes preparing to land at an airport with only one runway. For airplane $i$, it arrives above the airport at time $T_{i}$. When it arrives, its remaining fuel allows it to keep circling for another $D_{i}$ units of time. That is, it can start landing as early as time $T_{i}$, and as late as time $T_{i}+D_{i}$. The landing process takes $L_{i}$ units of time.

When one airplane finishes landing, another airplane may start landing immediately at the same moment. However, no airplane may start landing before the previous airplane has finished landing.

Determine whether all $N$ airplanes can land safely.

Input Format

The input contains multiple test cases.

The first line contains an integer $T$, representing the number of test cases.

For each test case, the first line contains an integer $N$.

The following $N$ lines each contain three integers $T_{i}, D_{i}, L_{i}$.

Output Format

For each test case, output YES or NO, indicating whether all airplanes can land safely.

2
3
0 100 10
10 10 10
0 2 20
3
0 10 20
10 10 20
20 10 20

YES
NO

Hint

Sample Explanation

For the first test case, you can schedule airplane 3 to start landing at time 0 and finish at time 20. Schedule airplane 2 to start landing at time 20 and finish at time 30. Schedule airplane 1 to start landing at time 30 and finish at time 40.

For the second test case, no matter how you schedule, there will always be an airplane that cannot land in time.

Constraints and Notes

For $30\%$ of the testdata, $N \leq 2$.

For $100\%$ of the testdata, $1 \leq T \leq 10$, $1 \leq N \leq 10$, $0 \leq T_{i}, D_{i}, L_{i} \leq 10^{5}$.

Lanqiao Cup 2023 Provincial Contest B Group Problem D.

Translated by ChatGPT 5