Alien Invaders

Time limit3sMemory limit256 MB

Summary

Destroy each alien within its time window using bombs, where a bomb of power R kills all aliens present within distance R at cost R, for minimum total fuel.

Level: Medium7 of 10
Topics: Dynamic programming, Divide and conquer, Intervals, Sorting
Solved: No attempts yet

Problem

Aliens have invaded Earth. If you do not defend yourself, you die. Or you get assimilated. You might even get eaten. Nobody is quite sure which.

The aliens attack on a fixed schedule. There are $n$ aliens, and alien $i$ appears at time $a_i$ at distance $d_i$ and attacks you at time $b_i$ . You therefore have to destroy alien $i$ at some time between $a_i$ and $b_i$ , inclusive.

Your weapon is a photon bomb whose blast power you can set to any value. If you set the power to $R$ and detonate the bomb, every alien that is on the field at that moment and stands at distance at most $R$ dies instantly, and the bomb burns $R$ units of fuel. You may detonate a bomb at any time and as many times as you want.

Find the smallest amount of fuel that destroys every alien without letting any of them attack you.

Input

The first line has the number of test cases $T$ .

Each test case starts with a line holding the number of aliens $n$ $(1 \le n \le 300)$ . The next $n$ lines hold $a_i$ , $b_i$ , $d_i$ $(1 \le a_i < b_i \le 10000,\ 1 \le d_i \le 10000)$ for alien $i$ , separated by spaces.

Output

For each test case, print the smallest amount of fuel that destroys every alien, one answer per line. The answer is always an integer.

Examples2

Example 1
Input
```
1
3
1 4 4
4 7 5
3 4 7
```
Expected output
```
7
```
Example 2
Input
```
1
1
1 2 5
```
Expected output
```
5
```