You are given an undirected connected graph on $n$ vertices. Each edge of this graph has a weight; the weight of the edge connecting vertices $i$ and $j$ is $w_{i,j}$ (or $w_{i,j} = 0$ if there is no edge between $i$ and $j$). All weights are positive integers.

You are also given a positive integer $c$.

You have to build a spanning tree of this graph; i. e. choose exactly $(n-1)$ edges of this graph in such a way that every vertex can be reached from every other vertex by traversing some of the chosen edges. The cost of the spanning tree is the sum of two values:

• the sum of weights of all chosen edges;
• the maximum matching in the spanning tree (i. e. the maximum size of a set of edges such that they all belong to the chosen spanning tree, and no vertex has more than one incident edge in this set), multiplied by the given integer $c$.

Find any spanning tree with the minimum cost. Since the graph is connected, there exists at least one spanning tree.

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.

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