Description

deepl翻译

给你一个有 $n$ 个顶点的无向连接图。该图的每条边都有权重；连接顶点 $i$ 和 $j$ 的边的权重为 $w_{i,j}$ （如果 $i$ 和 $j$ 之间没有边，则权重为 $w_{i,j} = 0$ ）。所有权重均为正整数。

我们还给出了一个正整数 $c$ 。

您必须为该图建立一棵生成树，即在该图中精确选择 $(n-1)$ 条边，使得每个顶点都可以通过遍历所选的某些边从其他顶点到达。生成树的成本是两个值的总和：

• 所有选定边的权重之和；
• 生成树中的最大匹配数（即全部属于所选生成树的边集的最大大小，且该边集中没有一个顶点有多于一条的附带边），再乘以给定整数 $c$ 。

找出成本最小的生成树。由于图是连通的，因此至少存在一棵生成树。

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

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

21

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$.