Furniture Factory

A furniture factory employs $m$ workers in total. Every worker has exactly the same skill and productivity. Next month the factory must build $n$ pieces of furniture, and each piece $i$ comes with three values.

• $s_i$: the earliest time at which work on it may begin
• $w_i$: the total amount of work needed to finish it
• $d_i$: the deadline by which it must be finished ($d_i \ge s_i + w_i$)

In other words, piece $i$ can only be worked on from time $s_i$ onward, it is complete once $w_i$ units of work have been spent on it, and it must be finished no later than time $d_i$.

At any moment at most one worker may work on a given piece of furniture. Work may be paused and resumed later, and a paused piece may be picked up by a different worker. Every worker starts and stops on integer times, and time is written as $1, 2, 3, \dots, \max\{d_i\}$ for convenience.

Determine whether a production plan exists that finishes every piece of furniture by its own deadline.

The first line contains the number of test cases $T$. For each test case, the first line contains the number of workers $m$ and the number of pieces $n$ ($1 \le m \le 10$, $1 \le n \le 100$). The next $n$ lines each contain $s_i$, $w_i$, $d_i$ for one piece ($1 \le s_i < d_i \le 500$, $1 \le w_i \le d_i - s_i$).

For each test case, print one line: Yes if a production plan finishes every piece of furniture by its deadline, and No otherwise.