Description

Input

The first line contains two integers $n$ and $c$ ($2 \le n \le 20$; $1 \le c \le 10^6$).

Then $n$ lines follow. The $i$-th of them contains $n$ integers $w_{i,1}, w_{i,2}, \dots, w_{i,n}$ ($0 \le w_{i,j} \le 10^6$), where $w_{i,j}$ denotes the weight of the edge between $i$ and $j$ (or $w_{i,j} = 0$ if there is no such edge).

Additional constraints on the input:

• for every $i \in [1, n]$, $w_{i,i} = 0$;
• for every pair of integers $(i, j)$ such that $i \in [1, n]$ and $j \in [1, n]$, $w_{i,j} = w_{j,i}$;
• the given graph is connected.

Output

Print one integer — the minimum cost of a spanning tree of the given graph.

4 10
0 1 8 0
1 0 1 0
8 1 0 2
0 0 2 0

21

4 5
0 1 8 0
1 0 1 0
8 1 0 2
0 0 2 0

14

Note

In the first example, the minimum cost spanning tree consists of edges $(1, 3)$, $(2, 3)$ and $(3, 4)$. The maximum matching for it is $1$.

In the second example, the minimum cost spanning tree consists of edges $(1, 2)$, $(2, 3)$ and $(3, 4)$. The maximum matching for it is $2$.