William 非常喜欢拼图套件。在他的一个生日那天,他的朋友送给他一张完整的无向边加权图,由 $$$n$$$ 个顶点组成。
他想要构建该图的生成树,使得对于前$$$k$$$个顶点满足以下条件:索引为$$$i$$$的顶点的度不超过$$$d_i$$$。从 $$$k + 1$$$ 到 $$$n$$$ 的顶点可以有任意度数。
William 希望你找到满足所有条件的生成树的最小权值。
生成树是图的边的子集,它在图的所有 $$$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)$$$。
输出
打印一个整数:在给定度数约束下第一个 $$$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
输出 #1
95