Pimp My Ride

There are plenty of cars, motorcycles, trucks, and other vehicles on the streets that badly need refurbishment. You have taken on the job of restoring them, funded by a generous budget from a major TV station.

There is a lot of work to do, so you decide to hand off the individual tasks — painting, interior decoration, and so on — to specialized garages. Because each garage handles only certain kinds of work, different tasks go to different garages. Worse, a garage tends to charge more when the car already looks good: a painter, for example, may charge extra for a car whose interior is already all leather. Since these surcharges depend on which jobs have already been completed, you want to save money by finding an optimal order in which to perform the jobs.

The jobs are numbered $1$ through $n$. Each job $i$ has a base price, and for every ordered pair of jobs $(i, j)$ with $i \ne j$ there is a surcharge $s_{ij}$ (in US dollars): you must pay an additional $s_{ij}$ for job $i$ if and only if job $j$ was completed before job $i$. The total cost of a job order is the sum, over all jobs, of each job's base price plus the surcharges owed for the jobs already finished at the moment it is performed. Compute the minimum possible total cost to finish all jobs.

The first line contains the number of scenarios.

Each scenario starts with a line containing the number of jobs $n$ ($1 \le n \le 14$). The next $n$ lines describe the cost matrix, each containing exactly $n$ integers. On line $i$ (for $1 \le i \le n$), the $i$-th integer is the base price of job $i$, and the $j$-th integer (for $j \ne i$) is the surcharge for job $i$ that applies if job $j$ was completed before it. Every price and surcharge is a non-negative integer not exceeding $100000$.

For each scenario, first print a line:

Scenario #i:

where $i$ is the scenario number, counting from $1$. Then print a line:

You have officially been pimped for only $p

where $p$ is the minimum total cost. Print a blank line between consecutive scenarios.