Magazine Delivery

Time limit1sMemory limit128 MB

Summary

Three cars start at L1 and must deliver to locations in strict order 2,3,...,N, with only one car moving at a time; minimize the total completion time.

Level: Hard8 of 10
Topics: Dynamic programming, Shortest path, Implementation, Greedy
Solved: No attempts yet

Problem

A courier company in Tehran must deliver magazines to $N$ locations in the city, labeled $L_1$ through $L_N$ . The company assigns 3 cars to the job. At time $0$ , all 3 cars and the magazines are at $L_1$ . There are plenty of magazines at $L_1$ , and a car may load as many as it wants. A copy must be delivered to every location, subject to the following rules:

For every $i = 2, \dots, N$ , the delivery to $L_i$ may happen only after the delivery to $L_{i-1}$ is complete.
At any moment only one of the three cars is driving; the other two rest at their current locations.

The time for a car to travel between $L_i$ and $L_j$ (in either direction) is a positive integer $D_{i,j}$ .

Arrange the delivery schedule so that the time by which all $N$ locations have received magazines is minimized. Write a program to compute this minimum completion time.

Input

The input contains $M$ instances of the problem ( $1 \le M \le 10$ ). The first line is $M$ . The instances follow one after another.

Each instance begins with a line containing $N$ ( $N \le 30$ ). The next $N-1$ lines describe the distances: line $i$ (for $i = 1, \dots, N-1$ ) contains $D_{i,j}$ for $j = i+1, \dots, N$ , separated by spaces. Distances are symmetric ( $D_{i,j} = D_{j,i}$ ).

Output

Print $M$ lines, one per instance. Each line is the minimum time needed to deliver magazines to all $N$ locations of that instance.

Examples3

Example 1
Input
```
1
5
10 20 3 4
5 10 20
8 18
19
```
Expected output
```
22
```
Example 2
Input
```
1
1
```
Expected output
```
0
```
Example 3
Input
```
1
2
7
```
Expected output
```
7
```