This page is still under construction.

Parts of this page are still being built. What you see may change.

Fastest Route

Interview

Time limit8sMemory limit512 MB

Summary
Given N stages and N pieces of equipment, where clearing stage i yields equipment i and each stage can be done in any order with at most one equipment, find the minimum total time to clear all stages.
Level

Medium7 of 10

Topics
Dynamic programming, Bit manipulation, Greedy
Solved
No attempts yet

Problem

Your intellectual programming circle (known as the Intelligent Clever Programming Circle, ICPC) is in the middle of a big cleanup. The club room is crammed with all kinds of items left behind by generations of seniors. While organizing a shelf, you find a large stash of retro games sealed away in the back. Some of them look familiar, so you decide to play one again after a long time.

The details of the game you found are as follows.

The game has N stages numbered 1 through N, and you can clear them in any order. There are also pieces of equipment numbered 1 through N, and using them shortens the time needed to clear a stage. You start the game with no equipment, but clearing stage i gives you equipment i, and once obtained it can be used any number of times. You can use only one piece of equipment on a stage, but you can use the same equipment on different stages.

You have cleared this game before, so for each piece of equipment you know the time it takes to clear each stage when that equipment is used. Clearing it normally would be boring, so you decide to minimize the total time until all stages are cleared. Drawing on your ICPC experience, you decide to write a program that, given this information, computes the minimum time needed to clear all the stages.

Input

The input consists of multiple datasets. The end of the input is given by a line containing a single zero. Each dataset describes one game, in the following format.

N
t10 t11 ... t1N
t20 t21 ... t2N
...
tN0 tN1 ... tNN

The first line of a dataset contains a single integer N, the number of stages. The following N lines contain N+1 integers describing the clearing times of the stages. ti0 is the time needed to clear stage i without equipment. ti j (j > 0) is the time needed to clear stage i with equipment j.

Each value satisfies the following constraints.

  • 1 ≤ N ≤ 16
  • 1 ≤ ti j ≤ 100,000

Output

For each dataset, output on one line an integer representing the minimum time needed to clear all the stages. The output line must not contain any characters other than this number.

Examples1

  1. Example 1

    Input
    3
100 100 100 100
100 1 100 100
100 1 1 100
3
100 100 1 100
200 102 100 102
100 100 1 100
7
100 100 60 60 70 70 70 90
100 50 100 55 45 45 55 44
100 50 60 100 51 50 55 30
100 70 10 20 1 10 10 40
200 90 10 30 10 10 10 30
150 200 12 1 11 11 1 30
10000 1200 1100 1100 1200 1200 1090 1
0
    Expected output
    102
202
1301