CF1948G MST with Matching

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.

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