Under construction

Still being built. Things may change

Economic One-way Roads

Time limit5sMemory limit1024 MB

Summary
Given N up to 18 cities with a directed cost for each road direction, orient every road so all cities are mutually reachable at minimum total cost, or report -1.
Level

Hard8 of 10

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

Problem

The country of RUN has NN cities, some of which are connected by two-way roads. Each road connects two different cities, and no two roads connect the same pair of cities. It is not guaranteed that every city is reachable from every other city by traveling along some roads.

Due to traffic issues, the mayor of RUN decided to make all roads one-way. After doing so, it must be possible to move from any city to any other city using one or more roads. To save as much money as possible, the mayor will pick the cheapest orientation among all orientations that satisfy this condition. The cost of orienting a road depends on both the road itself and the direction it is oriented in.

Input

The first line contains the number of cities NN (2≤N≤182 \leq N \leq 18).

Each of the next NN lines contains NN space-separated integers. The jj-th integer in the (i+1)(i+1)-th line, aija_{ij}, is the cost of orienting the road from city ii to city jj, or −1-1 if no road connects these two cities.

For all ii, aii=−1a_{ii} = -1. For all distinct ii and jj, either aij=aji=−1a_{ij} = a_{ji} = -1, or 0≤aij,aji≤1060 \leq a_{ij}, a_{ji} \leq 10^6.

Output

Print the minimum cost needed to orient all roads so that the condition is satisfied. If no valid orientation exists, print −1-1.

Examples2

  1. Example 1

    Input
    4
-1 3 2 -1
3 -1 7 7
5 9 -1 9
-1 6 7 -1
    Expected output
    27

  2. Example 2

    Input
    6
-1 1 2 -1 -1 -1
3 -1 4 -1 -1 -1
5 6 -1 0 -1 -1
-1 -1 0 -1 6 5
-1 -1 -1 4 -1 3
-1 -1 -1 2 1 -1
    Expected output
    -1