H. Конструктор
ограничение по времени на тест
6 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Василий любит различные конструкторы. На один из дней рождения друзья ему подарили полный неориентированный взвешенный граф из $$$n$$$ вершин.

Он хочет построить такое остовное дерево этого графа, чтобы для первых $$$k$$$ вершин выполнялись следующие условия: степень вершины под номером $$$i$$$ не превышает $$$d_i$$$. У вершин от $$$k + 1$$$ до $$$n$$$ степени могут быть любыми.

Василий просит найти вас минимальный вес остовного дерева, подходящего под все условия.

Напомним, что остовным деревом называется подмножество ребер графа, образующее дерево на всех $$$n$$$ вершинах графа. Весом остовного дерева называется сумма весов ребер, входящих в остовное дерево.

Входные данные

Первая строка содержит два целых числа $$$n$$$ и $$$k$$$ ($$$2 \leq n \leq 50$$$, $$$1 \leq k \leq min(n - 1, 5)$$$).

Вторая строка содержит $$$k$$$ целых чисел $$$d_1, d_2, \ldots, d_k$$$ ($$$1 \leq d_i \leq n$$$).

$$$i$$$-я из следующих $$$n - 1$$$ строк содержит по $$$n - i$$$ целых чисел $$$w_{i,i+1}, w_{i,i+2}, \ldots, w_{i,n}$$$ ($$$1 \leq w_{i,j} \leq 100$$$) — веса ребер между вершинами $$$(i,i+1),(i,i+2),\ldots,(i,n)$$$.

Выходные данные

Выведите одно целое число — минимальный вес остовного дерева при заданных ограничениях на степени первых $$$k$$$ вершин.

Пример
Входные данные
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