Василий любит различные конструкторы. На один из дней рождения друзья ему подарили полный неориентированный взвешенный граф из \(n\) вершин.
Он хочет построить такое остовное дерево этого графа, чтобы для первых \(k\) вершин выполнялись следующие условия: степень вершины под номером \(i\) не превышает \(d_i\). У вершин от \(k + 1\) до \(n\) степени могут быть любыми.
Василий просит найти вас минимальный вес остовного дерева, подходящего под все условия.
Напомним, что остовным деревом называется подмножество ребер графа, образующее дерево на всех \(n\) вершинах графа. Весом остовного дерева называется сумма весов ребер, входящих в остовное дерево.
Выходные данные
Выведите одно целое число — минимальный вес остовного дерева при заданных ограничениях на степени первых \(k\) вершин.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
10 5
5 3 4 2 1
29 49 33 12 55 15 32 62 37
61 26 15 58 15 22 8 58
37 16 9 39 20 14 58
10 15 40 3 19 55
53 13 37 44 52
23 59 58 4
69 80 29
89 28
48
|
95
|