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;
  using ll = long long;
  template <class T>
  void read(T &x) {
    char ch;
    x = 0;
    int f = 1;
    while (isspace(ch = getchar_unlocked()))
      ;
    if (ch == '-') ch = getchar_unlocked(), f = -1;
    do x = x * 10 + (ch - '0');
    while (isdigit(ch = getchar_unlocked()));
    x *= f;
  }
  template <class T, class... A>
  void read(T &x, A &...args) {
    read(x);
    read(args...);
  }
  template <size_t N>
  struct DSU {
    int fa[N];
    void clear() { memset(fa, 0, sizeof(fa)); }
    int find(int x) { return !fa[x] ? x : fa[x] = find(fa[x]); }
    bool join(int x, int y) {
      x = find(x), y = find(y);
      if (x == y) return false;
      fa[x] = y;
      return true;
    }
  };
  const int N = 55;
  const int MAXE = 280;
  const int INF = 0x3f3f3f3f;
  struct edge {
    int u, v, w;
    edge() = default;
    edge(int _u, int _v, int _w) : u(_u), v(_v), w(_w) {}
    bool operator<(const edge &rhs) const { return w < rhs.w; }
  };
  vector<edge> S, E1, E2, E;
  vector<edge> special;
  DSU<N> D;
  int fa[5];
  int find(int x) {
    while (fa[x]) x = fa[x];
    return x;
  }
  int res = INF;
  bool I[MAXE], T[MAXE];
  pair<int, int> d[MAXE];
  int pre[MAXE];
  int deg[MAXE], lim[MAXE];
  int wt[MAXE];
  bool vis[MAXE];
  int n, k;
  void flip(int u) {
    I[u] ^= 1;
    if (I[u])
      ++deg[E[u].u], ++deg[E[u].v];
    else
      --deg[E[u].u], --deg[E[u].v];
  }
  vector<pair<int, int>> G;
  int augment() {
    memset(pre, -1, sizeof(pre));
    int ec = E.size();
    for (int i = 0; i < ec; ++i) wt[i] = I[i] ? -E[i].w : E[i].w;
    bool up = true;
    for (int i = 0; i < ec && up; ++i) {
      up = false;
      for (const auto &[x, y] : G) {
        pair<int, int> tp = {d[x].first + wt[y], d[x].second + 1};
        if (tp < d[y]) d[y] = tp, pre[y] = x, up = true;
      }
    }
    pair<int, int> val = {INF, INF};
    int u = -1;
    for (int i = 0; i < ec; ++i)
      if (T[i] && d[i] < val) val = d[i], u = i;
    if (val.first > 1e8) return INF;
    do flip(u);
    while ((u = pre[u]) != -1);
    return val.first;
  }
  int MI(int val) {
    memset(deg, 0, sizeof(deg));
    memset(I, 0, sizeof(I));
    for (const auto &e : special) ++deg[e.u], ++deg[e.v];
    for (int i = 0; i < k; ++i)
      if (deg[i] > lim[i]) return INF;
    int card = special.size();
    const int ec = E.size();
    while (true) {
      D.clear();
      for (const auto &e : special) D.join(e.u, e.v);
      for (int i = 0; i < ec; ++i)
        if (I[i]) D.join(E[i].u, E[i].v);
      fill(d, d + ec, make_pair(INF, 0));
      memset(T, 0, sizeof(T));
      for (int i = 0; i < ec; ++i)
        if (!I[i] && D.find(E[i].u) != D.find(E[i].v)) d[i] = {E[i].w, 0};
      for (int i = 0; i < ec; ++i)
        if (!I[i] && deg[E[i].u] < lim[E[i].u] && deg[E[i].v] < lim[E[i].v])
          T[i] = true;
      G.clear();
      for (int i = 0; i < ec; ++i) {
        if (!I[i]) continue;
        D.clear();
        for (const auto &e : special) D.join(e.u, e.v);
        --deg[E[i].u];
        --deg[E[i].v];
        for (int j = 0; j < ec; ++j)
          if (j != i && I[j]) D.join(E[j].u, E[j].v);
        for (int j = 0; j < ec; ++j)
          if (!I[j] && D.find(E[j].u) != D.find(E[j].v)) G.emplace_back(i, j);
        for (int j = 0; j < ec; ++j)
          if (!I[j] && deg[E[j].u] < lim[E[j].u] && deg[E[j].v] < lim[E[j].v])
            G.emplace_back(j, i);
        ++deg[E[i].u];
        ++deg[E[i].v];
      }
      int ret = augment();
      if (ret == INF) break;
      val += ret;
      ++card;
    }
    if (card < n - 1) return INF;
    return val;
  }
  void DFS(vector<edge>::const_iterator it, int sum = 0) {
    if (it == end(S)) {
      res = min(res, MI(sum));
      return;
    }
    int fu = find(it->u), fv = find(it->v);
    DFS(next(it), sum);
    if (fu != fv) {
      fa[fu] = fv;
      special.push_back(*it);
      DFS(next(it), sum + it->w);
      special.pop_back();
      fa[fu] = 0;
    }
  }
  int main() {
    read(n, k);
    for (int i = 0; i < k; ++i) read(lim[i]);
    fill(lim + k, lim + n, INF);
    for (int u = 0; u < n; ++u)
      for (int v = u + 1; v < n; ++v) {
        int wt;
        read(wt);
        if (u < k && v < k)
          S.emplace_back(u, v, wt);
        else if (u < k && v > k)
          E1.emplace_back(u, v, wt);
        else
          E2.emplace_back(u, v, wt);
      }
    sort(begin(E2), end(E2));
    for (const auto &e : E2)
      if (D.join(e.u, e.v)) E.push_back(e);
    E.insert(E.end(), begin(E1), end(E1));
    DFS(begin(S));
    printf("%d\n", res);
    return 0;
  }
  