외계 침략자

시간 제한3초메모리 제한256 MB

요약

각 외계인은 정해진 시간 구간 안에 파괴해야 하며 위력 R인 폭탄은 R만큼 연료를 소모하고 터뜨린 시각에 있으면서 거리가 R 이하인 외계인을 모두 제거하므로 총 연료가 최소가 되도록 배치합니다.

난이도: 보통10점 중 7점
유형: 동적 계획법, 분할 정복, 구간, 정렬
정답자: 아직 제출이 없습니다

문제

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

외계인의 공격 방식은 이렇다. 외계인은 모두 $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)$ 가 공백으로 구분되어 주어진다.

출력

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

예제2

예제 1
입력
```
1
3
1 4 4
4 7 5
3 4 7
```
예상 출력
```
7
```
예제 2
입력
```
1
1
1 2 5
```
예상 출력
```
5
```