A Lazy Worker

There is a lazy worker who wants to do as little work as possible. He is under one constraint: whenever there is a job he is able to work on, he must be busy working.

There are jobs $1, 2, \dots, n$, and job $i$ has processing time $t_i$. Job $i$ arrives at time $a_i$ and has deadline $d_i$, where $t_i$, $a_i$, and $d_i$ are nonnegative integers. Every job has a hard deadline: job $i$ may only be executed inside its allowed interval $I_i = [a_i, d_i]$, so it must start no earlier than $a_i$ and finish no later than $d_i$.

The worker handles only one job at a time, and once a job is started it runs to completion without interruption. When a job finishes, the worker must immediately begin another job if one is available. If no job is available, the worker stays idle and starts a job as soon as one becomes available.

For every job $i$ the interval length $d_i - a_i$ is at least $t_i$ and strictly less than $2 t_i$.

The worker may choose which of the available jobs to run next, and different choices may cause some jobs to miss their deadlines and never be executed. Write a program that finds the minimum possible total time the worker spends working, that is, the minimum possible sum of processing times over the jobs he actually executes.

The input consists of $T$ test cases. The first line contains the number of test cases $T$.

The first line of each test case contains the number of jobs $n$ ($0 \le n \le 100$). Each of the next $n$ lines contains three integers: the processing time $t_i$, the arrival time $a_i$, and the deadline $d_i$ of one job. The values satisfy $1 \le t_i$, $0 \le a_i \le 250$, $1 \le d_i \le 250$, and each job satisfies $t_i \le d_i - a_i < 2 t_i$.

For each test case, print exactly one line containing the minimum total amount of time the worker spends working.