Дан неориентированный связный граф, в котором \(n\) вершин. У каждого ребра этого графа есть вес; вес ребра между вершинами \(i\) и \(j\) равен \(w_{i,j}\) (или \(w_{i,j} = 0\), что означает, что между \(i\) и \(j\) нет ребра). Все веса — положительные целые числа.
Также дано положительное целое число \(c\).
Вы должны построить остовное дерево для этого графа, то есть выбрать ровно \((n-1)\) ребер графа так, чтобы можно было из любой вершины добраться до любой другой по выбранным ребрам. Стоимость остовного дерева — это сумма двух значений:
- сумма весов всех выбранных ребер;
- максимальное паросочетание в остовном дереве (то есть максимальный размер множества ребер, такого, что каждое ребро принадлежит остовному дереву и каждой вершине инцидентно не более одного ребра из множества), умноженное на заданное число \(c\).
Найдите любое остовное дерево с минимальной стоимостью. Так как граф связный, у него существует хотя бы одно остовное дерево.
Выходные данные
Выведите одно целое число — минимальную стоимость остовного дерева.
Примечание
В первом примере минимальное остовное дерево состоит из ребер \((1, 3)\), \((2, 3)\) и \((3, 4)\). Максимальное паросочетание относительно него равно \(1\).
Во втором примере минимальное остовное дерево состоит из ребер \((1, 2)\), \((2, 3)\) и \((3, 4)\). Максимальное паросочетание относительно него равно \(2\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 10
0 1 8 0
1 0 1 0
8 1 0 2
0 0 2 0
|
21
|
|
2
|
4 5
0 1 8 0
1 0 1 0
8 1 0 2
0 0 2 0
|
14
|