CF1556H.DIY Tree

William really likes puzzle kits. For one of his birthdays, his friends gifted him a complete undirected edge-weighted graph consisting of $n$ vertices.

He wants to build a spanning tree of this graph, such that for the first $k$ vertices the following condition is satisfied: the degree of a vertex with index $i$ does not exceed $d_i$. Vertices from $k + 1$ to $n$ may have any degree.

William wants you to find the minimum weight of a spanning tree that satisfies all the conditions.

A spanning tree is a subset of edges of a graph that forms a tree on all $n$ vertices of the graph. The weight of a spanning tree is defined as the sum of weights of all the edges included in a spanning tree.

威廉非常喜欢拼图套件。在他某次生日时，朋友们送给他一个由 $n$ 个顶点构成的无向带权完全图。

他希望在该图中构造一棵生成树，使得对前 $k$ 个顶点满足如下条件：编号为 $i$ 的顶点的度数不超过 $d_i$。而编号从 $k + 1$ 到 $n$ 的顶点则对度数不作限制。

威廉希望你找出满足所有上述条件的生成树的最小总权重。

生成树是图中边的一个子集，它在图的所有 $n$ 个顶点上构成一棵树。生成树的权重定义为其中所包含的所有边的权重之和。

The first line of input contains two integers $n$, $k$ ($2 \leq n \leq 50$, $1 \leq k \leq min(n - 1, 5)$).

The second line contains $k$ integers $d_1, d_2, \ldots, d_k$ ($1 \leq d_i \leq n$).

The $i$-th of the next $n - 1$ lines contains $n - i$ integers $w_{i,i+1}, w_{i,i+2}, \ldots, w_{i,n}$ ($1 \leq w_{i,j} \leq 100$): weights of edges $(i,i+1),(i,i+2),\ldots,(i,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$）。

接下来的 $n - 1$ 行中，第 $i$ 行包含 $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)$ 的权重。

Print one integer: the minimum weight of a spanning tree under given degree constraints for the first $k$ vertices.

输出一个整数：在给定前 $k$ 个顶点的度数约束下，生成树的最小权重。