Problem

**hidden**## STSP - Small TSP

You're given a complete, directed, weighted graph with N vertices. Find the length of the shortest possible route visiting all the vertices exactly once, and returns to the original vertex.

### Input

The first line of input contains an integer N, the number of vertices. (N ≤ 18)

The rest of the input contains the (NxN) adjacency matrix of the graph.

The (i + 1)-th row, j-th column of the input contains the weight w(i, j) of the directed edge (i, j). (0 ≤ w(i, j) ≤ 1000000, w(i, i) = 0)

### Output

To the first and only line of output print the desired length.

### Example

Input:30 1 22 0 12 2 03 0 1 2 2 0 1 2 2 0Output:4

Added by: | gustav |

Date: | 2014-12-05 |

Time limit: | 5s |

Source limit: | 50000B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Languages: | All except: ASM64 |

Resource: | classical problem |