题目描述

有一个工人，由于懒惰，可能缺乏以最高效率工作的动力。他希望尽量减少自己的工作量（他很懒惰，但有一个限制条件，即只要有他能做的工作，他就必须处于忙碌状态）。

我们考虑一组任务，编号为 $1, 2, \cdots, n$，它们的处理时间分别为 $t_1, t_2, \cdots, t_n$。任务 $i$ 在时间 $a_i$ 到达，并在时间 $d_i$ 截止。我们假设 $t_i$、$a_i$ 和 $d_i$ 均为非负整数值。这些任务具有严格的截止时间，这意味着每个任务 $i$ 只能在其允许的时间区间 $I_i = [a_i, d_i]$ 内执行。这些任务由该工人执行，且工人一次只能执行一个任务。一旦一个任务开始执行，就必须不间断地完成。当一个任务完成后，如果有其他任务可以执行，必须立即开始执行下一个任务。否则，工人处于空闲状态，并在有任务到达时立即开始执行。需要注意的是，对于每个任务 $i$，时间区间 $I_i$ 的长度 $d_i - a_i$ 大于或等于 $t_i$，但小于 $2 \times t_i$。

编写一个程序，找出工人执行任务的最小总时间。

输入

输入包含 $T$ 个测试用例。测试用例的数量 $T$ 在输入文件的第一行给出。每个测试用例的第一行给出任务的数量 $n$（$0 \leq n \leq 100$），接下来的 $n$ 行每行包含三个整数，分别表示每个任务的处理时间 $t_i$（$1 \leq t_i \leq 20$）、到达时间 $a_i$（$0 \leq a_i \leq 250$）和截止时间 $d_i$（$1 \leq d_i \leq 250$）。

输出

每个测试用例精确地输出一行。输出应包含工人工作的总时间。

输入样例

3
3
15 0 25
50 0 90
45 15 70
3
15 5 20
15 25 40
15 45 60
5
3 3 6
3 6 10
3 14 19
6 7 16
4 4 11

输出样例

50
45
15

题目来源

Taejon 2002