description: <image>
  
  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.
  
  Input
  
  The first line of input contains two integers n, k (2 ≤ n ≤ 50, 1 ≤ k ≤ min(n - 1, 5)).
  
  The second line contains k integers d_1, d_2, …, d_k (1 ≤ d_i ≤ n). 
  
  The i-th of the next n - 1 lines contains n - i integers w_{i,i+1}, w_{i,i+2}, …, w_{i,n} (1 ≤ w_{i,j} ≤ 100): weights of edges (i,i+1),(i,i+2),…,(i,n).
  
  Output
  
  Print one integer: the minimum weight of a spanning tree under given degree constraints for the first k vertices. 
  
  Example
  
  Input
  
  
  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
  
  
  Output
  
  
  95
solution: #include <bits/stdc++.h>
  using namespace std;
  const int maxn = 55, maxm = 1250, inf = 2e9;
  int n, K, m, N, D[maxn], w[maxn][maxn], id[maxn][maxn], wei[maxm];
  int C[maxn], fa[maxn], dis[maxm], ce[maxm], pre[maxm];
  int dd[maxm][2], ans = inf;
  bool in[maxn][maxn], inq[maxm];
  pair<int, int> E[maxn], F[maxn];
  vector<int> G[maxm];
  int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
  void brute(int x, int y) {
    if (x > K) {
      for (int i = int(1); i <= int(K); i++) fa[i] = i;
      for (int i = int(1); i <= int(K); i++) C[i] = 0;
      for (int i = int(1); i <= int(m); i++) {
        int x = E[i].first;
        int y = E[i].second;
        if (++C[x] > D[x]) return;
        if (++C[y] > D[y]) return;
        x = find(x);
        y = find(y);
        if (x == y) return;
        fa[x] = y;
      }
      memset(in, 0, sizeof(in));
      int s = 0;
      for (int i = int(1); i <= int(m); i++) s += w[E[i].first][E[i].second];
      while (1) {
        if (s >= ans) return;
        int r = 0;
        for (int i = int(1); i <= int(m); i++) F[i] = E[i];
        for (int i = int(1); i <= int(n); i++)
          for (int j = int(max(K, i) + 1); j <= int(n); j++)
            if (in[i][j]) F[(++r) + m] = {i, j};
        for (int i = int(1); i <= int(N); i++) G[i].clear();
        for (int i = int(m + 1); i <= int(m + r); i++) {
          iota(fa + 1, fa + n + 1, 1);
          fill(C + 1, C + n + 1, 0);
          for (int j = int(1); j <= int(m + r); j++)
            if (j != i) {
              int x = F[j].first, y = F[j].second;
              C[x]++, C[y]++, fa[find(x)] = find(y);
            }
          int I = id[F[i].first][F[i].second];
          wei[I] = -w[F[i].first][F[i].second];
          for (int i = int(1); i <= int(n); i++)
            for (int j = int(max(K, i) + 1); j <= int(n); j++)
              if (!in[i][j]) {
                if (C[i] < D[i]) G[id[i][j]].push_back(I);
                if (find(i) != find(j)) G[I].push_back(id[i][j]);
              }
        }
        for (int i = int(1); i <= int(n); i++)
          for (int j = int(max(K, i) + 1); j <= int(n); j++)
            if (!in[i][j]) {
              wei[id[i][j]] = w[i][j];
            }
        iota(fa + 1, fa + n + 1, 1);
        fill(C + 1, C + n + 1, 0);
        for (int i = int(1); i <= int(m + r); i++) {
          int x = F[i].first, y = F[i].second;
          C[x]++, C[y]++, fa[find(x)] = find(y);
        }
        for (int i = int(1); i <= int(N); i++)
          dis[i] = inf, ce[i] = 0, pre[i] = 0;
        queue<int> Q;
        for (int i = int(1); i <= int(n); i++)
          for (int j = int(max(K, i) + 1); j <= int(n); j++)
            if (!in[i][j]) {
              if (find(i) != find(j)) {
                dis[id[i][j]] = w[i][j], Q.push(id[i][j]), inq[id[i][j]] = 1;
              }
            }
        while (!Q.empty()) {
          int u = Q.front();
          Q.pop();
          for (int v : G[u])
            if (dis[v] > dis[u] + wei[v] ||
                (dis[v] == dis[u] + wei[v] && ce[v] > ce[u] + 1)) {
              pre[v] = u, dis[v] = dis[u] + wei[v], ce[v] = ce[u] + 1;
              if (!inq[v]) Q.push(v);
            }
          inq[u] = 0;
        }
        int _dis = inf, _ce = 0, x = 0;
        for (int i = int(1); i <= int(n); i++)
          for (int j = int(max(K, i) + 1); j <= int(n); j++)
            if (!in[i][j]) {
              if (C[i] < D[i] &&
                  (_dis > dis[id[i][j]] ||
                   (_dis == dis[id[i][j]] && _ce > ce[id[i][j]]))) {
                x = id[i][j], _dis = dis[id[i][j]], _ce = ce[id[i][j]];
              }
            }
        if (!x) {
          if (m + r == n - 1) {
            ans = s;
          }
          return;
        }
        while (x) {
          in[dd[x][0]][dd[x][1]] ^= 1;
          s += wei[x];
          x = pre[x];
        }
      }
    }
    if (y > K) {
      brute(x + 1, x + 2);
      return;
    }
    brute(x, y + 1);
    E[++m] = {x, y}, brute(x, y + 1), --m;
  }
  int main() {
    scanf("%d %d", &n, &K);
    for (int i = int(1); i <= int(K); i++) {
      scanf("%d", &D[i]);
    }
    for (int i = int(K + 1); i <= int(n); i++) D[i] = n;
    for (int i = int(1); i <= int(n); i++)
      for (int j = int(i + 1); j <= int(n); j++) {
        id[i][j] = ++N;
        dd[N][0] = i, dd[N][1] = j;
        scanf("%d", &w[i][j]);
      }
    brute(1, 2);
    printf("%d\n", ans);
    return 0;
  }
  