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;
  int w[maxn][maxn], d[maxn];
  struct edge {
    int u, v, w;
    bool operator<(const edge& a) const { return w < a.w; }
  };
  struct node {
    int to, w, nex;
  } buf[maxn * 2];
  int h[maxn], buf_tot;
  void add_edge(int u, int v, int w) {
    buf[++buf_tot] = (node){v, w, h[u]};
    h[u] = buf_tot;
  }
  struct node2 {
    int to, nex;
  } buf2[maxn * maxn * 12];
  int h2[maxn * 6], buf2_tot;
  void add_edge2(int u, int v) {
    buf2[++buf2_tot] = (node2){v, h2[u]};
    h2[u] = buf2_tot;
  }
  int I[maxn * 6];
  int pre[maxn], pre_id[maxn], rt[maxn], dep[maxn], deg[maxn];
  void dfs(int u, int p, int r) {
    rt[u] = r;
    for (int i = h[u]; i; i = buf[i].nex) {
      int v = buf[i].to;
      if (v == p) continue;
      pre[v] = u;
      pre_id[v] = buf[i].w;
      dep[v] = dep[u] + 1;
      dfs(v, u, r);
    }
  }
  int pa[maxn];
  int fnd(int u) { return u == pa[u] ? u : (pa[u] = fnd(pa[u])); }
  int X2[maxn * 6], dis_w[maxn * 6], dis_num[maxn * 6], dis_pre[maxn * 6];
  int vis[maxn * 6], cnt[maxn * 6];
  int main(void) {
    int n, k;
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= k; i++) scanf("%d", &d[i]);
    for (int i = 1; i <= n; i++) {
      for (int j = i + 1; j <= n; j++) scanf("%d", &w[i][j]);
    }
    for (int i = k + 1; i <= n; i++) d[i] = n;
    for (int i = k + 1; i <= n; i++) pa[i] = i;
    vector<edge> e;
    for (int i = k + 1; i <= n; i++)
      for (int j = i + 1; j <= n; j++) e.push_back((edge){i, j, w[i][j]});
    sort(e.begin(), e.end());
    vector<edge> U;
    for (int i = 0; i < (int)e.size(); i++) {
      int u = fnd(e[i].u), v = fnd(e[i].v);
      if (u == v) continue;
      U.push_back(e[i]);
      pa[u] = v;
    }
    for (int i = 1; i <= k; i++) {
      for (int j = k + 1; j <= n; j++) U.push_back((edge){i, j, w[i][j]});
    }
    vector<edge> V;
    for (int i = 1; i <= k; i++) {
      for (int j = i + 1; j <= k; j++) V.push_back((edge){i, j, w[i][j]});
    }
    int ans = (int)1e9;
    for (int sv = 0, sz = (1 << V.size()); sv < sz; sv++) {
      for (int i = 1; i <= k; i++) pa[i] = i;
      for (int i = 1; i <= n; i++) deg[i] = 0;
      int ok = 1;
      for (int j = 0; j < (int)V.size(); j++)
        if ((sv >> j) & 1) {
          int u = fnd(V[j].u), v = fnd(V[j].v);
          if (u == v) {
            ok = 0;
            break;
          }
          pa[u] = v;
          deg[V[j].u]++, deg[V[j].v]++;
        }
      for (int i = 1; i <= k; i++)
        if (deg[i] > d[i]) ok = 0;
      if (!ok) continue;
      for (int i = 0; i < U.size(); i++) I[i] = 0;
      while (1) {
        buf_tot = 0;
        for (int i = 1; i <= n; i++)
          h[i] = pre[i] = pre_id[i] = dep[i] = rt[i] = 0;
        for (int j = 0; j < (int)V.size(); j++)
          if ((sv >> j) & 1) {
            int u = V[j].u, v = V[j].v;
            add_edge(u, v, -1);
            add_edge(v, u, -1);
          }
        for (int j = 0; j < (int)U.size(); j++)
          if (I[j]) {
            int u = U[j].u, v = U[j].v;
            add_edge(u, v, j);
            add_edge(v, u, j);
          }
        for (int i = 1; i <= n; i++)
          if (pre[i] == 0) dfs(i, 0, i);
        buf2_tot = 0;
        for (int i = 0; i < (int)U.size(); i++) h2[i] = 0;
        vector<int> IP;
        for (int a = 0; a < (int)U.size(); a++)
          if (I[a]) {
            IP.push_back(a);
            for (int b = 0; b < (int)U.size(); b++)
              if (!I[b]) {
                deg[U[a].u]--, deg[U[a].v]--;
                deg[U[b].u]++, deg[U[b].v]++;
                if (deg[U[b].u] <= d[U[b].u] && deg[U[b].v] <= d[U[b].v]) {
                  add_edge2(a, b);
                }
                deg[U[a].u]++, deg[U[a].v]++;
                deg[U[b].u]--, deg[U[b].v]--;
              }
          }
        for (int b = 0; b < (int)U.size(); b++)
          if (!I[b]) {
            int u = U[b].u, v = U[b].v;
            if (rt[u] != rt[v]) {
              for (auto a : IP) {
                add_edge2(b, a);
              }
            } else {
              while (u != v) {
                if (dep[u] > dep[v]) {
                  if (~pre_id[u]) add_edge2(b, pre_id[u]);
                  u = pre[u];
                } else {
                  if (~pre_id[v]) add_edge2(b, pre_id[v]);
                  v = pre[v];
                }
              }
            }
          }
        for (int e = 0; e < U.size(); e++) {
          dis_w[e] = (int)1e9;
          dis_num[e] = 0;
          dis_pre[e] = -1;
          vis[e] = 0;
          cnt[e] = 0;
        }
        queue<int> Q;
        for (int i = 0; i < U.size(); i++) X2[i] = 0;
        for (int e = 0; e < U.size(); e++)
          if (!I[e]) {
            if (deg[U[e].u] + 1 <= d[U[e].u] && deg[U[e].v] + 1 <= d[U[e].v]) {
              Q.push(e);
              cnt[e]++;
              dis_w[e] = U[e].w, dis_num[e] = 0;
            }
            if (rt[U[e].u] != rt[U[e].v]) X2[e] = 1;
          }
        while (!Q.empty()) {
          int e = Q.front();
          Q.pop();
          vis[e] = false;
          for (int i = h2[e]; i; i = buf2[i].nex) {
            int v = buf2[i].to;
            int w = I[v] ? -U[v].w : U[v].w;
            if (dis_w[v] > dis_w[e] + w ||
                (dis_w[v] == dis_w[e] + w && dis_num[v] > dis_num[e] + 1)) {
              dis_w[v] = dis_w[e] + w;
              dis_num[v] = dis_num[e] + 1;
              dis_pre[v] = e;
              if (!vis[v]) {
                vis[v] = true;
                Q.push(v);
                if (++cnt[v] > U.size()) {
                  assert(0);
                }
              }
            }
          }
        }
        int e = -1, min_dis = (int)1e9, min_num = 0;
        for (int i = 0; i < U.size(); i++)
          if (X2[i]) {
            if (dis_w[i] < min_dis ||
                (dis_w[i] == min_dis && dis_num[i] < min_num)) {
              e = i;
              min_dis = dis_w[i], min_num = dis_num[i];
            }
          }
        if (min_dis == (int)1e9) break;
        while (~e) {
          if (I[e])
            deg[U[e].u]--, deg[U[e].v]--;
          else
            deg[U[e].u]++, deg[U[e].v]++;
          I[e] ^= 1;
          e = dis_pre[e];
        }
      }
      for (int i = 1; i <= n; i++) pa[i] = i, deg[i] = 0;
      int cnt = 0, tmp = 0;
      for (int j = 0; j < V.size(); j++)
        if ((sv >> j) & 1) {
          int u = fnd(V[j].u), v = fnd(V[j].v);
          assert(u != v);
          pa[u] = v;
          deg[V[j].u]++, deg[V[j].v]++;
          tmp += V[j].w;
          cnt++;
        }
      for (int j = 0; j < U.size(); j++)
        if (I[j]) {
          int u = fnd(U[j].u), v = fnd(U[j].v);
          assert(u != v);
          pa[u] = v;
          deg[U[j].u]++, deg[U[j].v]++;
          tmp += U[j].w;
          cnt++;
        }
      if (cnt < n - 1) continue;
      for (int i = 1; i <= n; i++) assert(fnd(i) == fnd(1));
      for (int i = 1; i <= n; i++) assert(deg[i] <= d[i]);
      ans = min(ans, tmp);
    }
    printf("%d\n", ans);
    return 0;
  }
  