게으른 일꾼

게으른 일꾼이 한 명 있다. 그는 가능한 한 적게 일하고 싶어 하지만, 지금 처리할 수 있는 일이 하나라도 있는 동안에는 반드시 일을 하고 있어야 한다는 제약을 받는다.

작업 $1, 2, \dots, n$ 이 있고, 작업 $i$ 의 처리 시간은 $t_i$ 이다. 작업 $i$ 는 시각 $a_i$ 에 도착하고 마감 시각은 $d_i$ 이며, $t_i$, $a_i$, $d_i$ 는 모두 음이 아닌 정수이다. 각 작업은 엄격한 마감을 가진다. 즉 작업 $i$ 는 자신의 허용 구간 $I_i = [a_i, d_i]$ 안에서만 실행할 수 있으며, $a_i$ 이후에 시작해서 $d_i$ 까지 끝나야 한다.

일꾼은 한 번에 하나의 작업만 처리하고, 한 번 시작한 작업은 중간에 멈추지 않고 끝까지 처리한다. 어떤 작업을 끝냈을 때 처리할 수 있는 다른 작업이 있으면 즉시 그 작업을 시작해야 한다. 처리할 수 있는 작업이 없으면 일꾼은 쉬고, 처리할 수 있는 작업이 도착하는 즉시 그 작업을 시작한다.

모든 작업 $i$ 에 대해, 구간의 길이 $d_i - a_i$ 는 $t_i$ 이상이고 $2 t_i$ 미만임이 보장된다.

일꾼은 처리할 수 있는 여러 작업 중 어느 것을 먼저 할지 선택할 수 있고, 이 선택에 따라 어떤 작업들은 마감을 넘겨 실행되지 못할 수 있다. 일꾼이 실제로 일에 쓴 시간의 총합, 즉 실행한 작업들의 처리 시간의 합을 최소로 만들 때 그 최솟값을 구하는 프로그램을 작성하라.

입력은 $T$ 개의 테스트 케이스로 이루어진다. 첫 줄에 테스트 케이스의 수 $T$ 가 주어진다.

각 테스트 케이스의 첫 줄에는 작업의 수 $n$ ($0 \le n \le 100$) 이 주어진다. 이어지는 $n$ 개의 줄에는 각 작업의 처리 시간 $t_i$, 도착 시각 $a_i$, 마감 시각 $d_i$ 가 세 정수로 주어진다. 모든 값은 $1 \le t_i$, $0 \le a_i \le 250$, $1 \le d_i \le 250$ 을 만족하며, 각 작업은 $t_i \le d_i - a_i < 2 t_i$ 를 만족한다.

각 테스트 케이스마다 정확히 한 줄을 출력한다. 그 줄에는 일꾼이 일에 쓴 시간 총합의 최솟값을 출력한다.