외계 침략자

외계인이 지구를 침략했다. 스스로 방어하지 않으면 죽는다. 동화될 수도 있고, 먹힐 수도 있다. 어느 쪽인지는 정확히 모르겠다.

외계인의 공격 방식은 이렇다. 외계인은 모두 $n$명이고, $i$번 외계인은 시각 $a_i$에 거리 $d_i$ 지점에 나타나 시각 $b_i$에 당신을 공격한다. 그러므로 $i$번 외계인은 $a_i$ 이상 $b_i$ 이하인 시각에 처치해야 한다.

당신의 무기는 광자폭탄이고, 폭발력을 원하는 값으로 맞출 수 있다. 폭발력을 $R$로 맞춰 터뜨리면 그 시각에 나타나 있는 외계인 가운데 거리가 $R$ 이하인 외계인이 모두 즉사하고, 연료를 $R$만큼 쓴다. 폭탄은 아무 시각에나, 원하는 횟수만큼 터뜨릴 수 있다.

한 번도 공격당하지 않고 외계인을 모두 처치하는 데 드는 연료의 최솟값을 구하여라.

첫 줄에 테스트 케이스의 수 $T$가 주어진다.

각 테스트 케이스의 첫 줄에는 외계인의 수 $n$ $(1 \le n \le 300)$이 주어진다. 이어지는 $n$개의 줄에는 $i$번 외계인의 $a_i$, $b_i$, $d_i$ $(1 \le a_i < b_i \le 10000,\ 1 \le d_i \le 10000)$가 공백으로 구분되어 주어진다.

각 테스트 케이스마다 외계인을 모두 처치하는 데 드는 연료의 최솟값을 한 줄에 하나씩 출력한다. 답은 항상 정수이다.