Minimum Cost to Visit Every Node

Prereq: Bitmask Introduction

Given a directed weighted graph as a 2D list where graph[i][j] is the edge weight from node i to node j (0 means no edge), find the minimum cost to visit every node starting from node 0. Each node must be visited exactly once, revisiting is not allowed, and there is no need to return to the start. Return -1 if visiting every node is impossible.

Input & Output

Input

graph — the adjacency matrix, where `graph[i][j]` is the weight of the edge from node `i` to node `j` and 0 means no edge

Output

the minimum total edge weight of a path that starts at node 0 and visits every node exactly once, or -1 if no such path exists

Example

Input

graph = [[0, 0, 1], [0, 0, 0], [0, 2, 0]]

Output

Explanation

Node 0 has only one outgoing edge, to node 2, costing 1. From node 2 the edge to node 1 costs 2. The path 0 → 2 → 1 visits all three nodes for a total of 3.

Example

Input

graph = [[0, 100, 100, 1], [0, 0, 100, 0], [0, 1, 0, 0], [0, 20, 1, 0]]

Output

Explanation

The path 0 → 3 → 2 → 1 costs 1 + 1 + 1 = 3. Taking the cheapest edge available at each step is not enough on its own here — the first hop to node 3 is cheap, but the payoff comes from the cheap edges 3 → 2 and 2 → 1 that it unlocks, while the other first hops cost 100.

Constraints

1 <= n <= 15, where n = graph.length
graph[i].length == n and graph[i][i] == 0
0 <= graph[i][j] <= 1000

Minimum Cost to Visit Every Node

Try it yourself