G. 带匹配的最小生成树

单个测试点时间限制：$6$ 秒 单个测试点内存限制：$512$ 兆字节

给定一张包含 $n$ 个顶点的无向连通图。图中每条边有一个权值，连接顶点 $i$ 和 $j$ 的边权为 $w_{i,j}$（若两点之间没有边，则 $w_{i,j}=0$）。所有边权均为正整数。

同时给定一个正整数 $c$。

你需要构造这张图的一棵生成树，即选出恰好 $n-1$ 条边，使得所有顶点两两连通。这棵生成树的代价为两个部分之和：

• 所选所有边的权值之和；
• 该生成树中的最大匹配的大小（即选出最多的一组边，满足任意两条边不共用顶点）乘以给定整数 $c$。

请找出代价最小的任意一棵生成树。题目保证图是连通的，因此至少存在一棵生成树。

输入格式

第一行包含两个整数 $n$ 和 $c$（$2\le n\le 20$；$1\le c\le 10^6$）。

接下来 $n$ 行，第 $i$ 行包含 $n$ 个整数 $w_{i,1},w_{i,2},\dots,w_{i,n}$（$0\le w_{i,j}\le 10^6$），其中 $w_{i,j}$ 表示顶点 $i$ 和 $j$ 之间的边权，$0$ 表示无边。

输入满足以下附加约束：

• 对任意 $i\in[1,n]$，有 $w_{i,i}=0$；
• 对任意整数对 $(i,j)$，有 $w_{i,j}=w_{j,i}$；
• 给定的图是连通的。

输出格式

输出一个整数，表示该图的生成树的最小代价。

样例输入

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

说明

在第一个样例中，最小代价生成树由边 $(1,3)$、$(2,3)$、$(3,4)$ 构成，其最大匹配大小为 $1$。

在第二个样例中，最小代价生成树由边 $(1,2)$、$(2,3)$、$(3,4)$ 构成，其最大匹配大小为 $2$。