Magazine Delivery

Time Limit: 2 Seconds
Memory Limit: 65536 KB

The TTT Taxi Service in Tehran is required to deliver some magazines to N locations
in Tehran. The locations are labeled L1 to LN. TTT assigns 3 cars for this service.
At time 0, all the 3 cars and magazines are located at L1. There are plenty
of magazines available in L1 and the cars can take as many as they want. Copies
of the magazine should be delivered to all locations, observing the following
rules:

1. For all i = 2 .. N, magazines should be delivered at Li only after magazines
are delivered at Li-1.

2. At any time, only one of the three cars is driving, and the other two are
resting in other locations.

The time to go from Li to Lj (or reverse) by any car is a positive integer denoted
by D[i , j].

The goal is to organize the delivery schedule for the cars such that the time
by which magazines are delivered to all N locations is minimum.

Write a program to compute the minimum delivery time.

**Input**

The input file contains M instances of this problem (1 <= M <= 10). The
first line of the input file is M. The descriptions of the input data follows
one after the other. Each instance starts with N in a single line (N <= 30).
Each line i of the following N-1 lines contains D[i , j], for all i=1..N-1,
and j=i+1..N.

**Output**

The output file contains M lines, each corresponding the solution to one of
the input data. In each line, the minimum time it takes to deliver the magazines
to all N locations is written.

**Sample Input**

1

5

10 20 3 4

5 10 20

8 18

19

**Sample Output**

22

Source:

**Asia 1999, Tehran (Iran)**
Submit
Status