G. MST с паросочетанием
ограничение по времени на тест
6 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан неориентированный связный граф, в котором $$$n$$$ вершин. У каждого ребра этого графа есть вес; вес ребра между вершинами $$$i$$$ и $$$j$$$ равен $$$w_{i,j}$$$ (или $$$w_{i,j} = 0$$$, что означает, что между $$$i$$$ и $$$j$$$ нет ребра). Все веса — положительные целые числа.

Также дано положительное целое число $$$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$$$ (или $$$w_{i,j} = 0$$$, если такого ребра нет).

Дополнительные ограничения на входные данные:

  • для каждого $$$i \in [1, n]$$$, $$$w_{i,i} = 0$$$;
  • для каждой пары целых чисел $$$(i, j)$$$, такой, что $$$i \in [1, n]$$$ и $$$j \in [1, n]$$$, выполняется $$$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$$$.