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;
  struct dsu {
    vector<int> id;
    dsu() {}
    dsu(int n) { id = vector<int>(n, -1); }
    int find(int a) {
      while (id[a] >= 0) {
        if (id[id[a]] >= 0) id[a] = id[id[a]];
        a = id[a];
      }
      return a;
    }
    bool unite(int a, int b) {
      a = find(a);
      b = find(b);
      if (a == b) return false;
      if (id[a] > id[b]) {
        swap(a, b);
      }
      id[a] += id[b];
      id[b] = a;
      return true;
    }
  };
  struct GroundSetElement {
    int x, y;
    int id;
    int cost;
    bool in_independent_set = false;
    int independent_set_position = -1;
    int parent = -1;
    GroundSetElement(int a, int b, int c) {
      x = a;
      y = b;
      cost = c;
    }
  };
  int n;
  vector<GroundSetElement> ground_set;
  vector<int> independent_set;
  vector<int> d;
  vector<int> limit;
  dsu g1;
  vector<pair<int, int>> other;
  vector<dsu> if_rem;
  bool graphic_matroid_oracle(int inserted) {
    const auto &e = ground_set[inserted];
    return g1.find(e.x) != g1.find(e.y);
  }
  bool graphic_matroid_oracle(int inserted, int removed) {
    const auto &e = ground_set[inserted];
    return if_rem[removed].find(e.x) != if_rem[removed].find(e.y);
  }
  bool matroid2_oracle(int inserted) {
    const auto &ei = ground_set[inserted];
    return d[ei.x] + 1 <= limit[ei.x] && d[ei.y] + 1 <= limit[ei.y];
  }
  bool matroid2_oracle(int inserted, int removed) {
    const auto &er = ground_set[removed];
    const auto &ei = ground_set[inserted];
    int degx = d[ei.x] + 1;
    int degy = d[ei.y] + 1;
    if (ei.x == er.x || ei.x == er.y) degx--;
    if (ei.y == er.x || ei.y == er.y) degy--;
    return degx <= limit[ei.x] && degy <= limit[ei.y];
  }
  void prepare_oracle1() {
    g1 = dsu(n);
    for (const auto &[x, y] : other) {
      g1.unite(x, y);
    }
    for (int id : independent_set) {
      const auto &e = ground_set[id];
      g1.unite(e.x, e.y);
    }
    if_rem.assign(ground_set.size(), dsu());
    for (int id : independent_set) {
      if_rem[id] = dsu(n);
      for (const auto &[x, y] : other) {
        if_rem[id].unite(x, y);
      }
      for (int id2 : independent_set) {
        if (id == id2) continue;
        const auto &e2 = ground_set[id2];
        if_rem[id].unite(e2.x, e2.y);
      }
    }
  }
  void prepare_oracle2() {
    d.assign(n, 0);
    for (int id : independent_set) {
      const auto &e = ground_set[id];
      d[e.x]++;
      d[e.y]++;
    }
  }
  bool augment() {
    prepare_oracle1();
    prepare_oracle2();
    const int SOURCE = -1;
    const int NOT_FOUND = -2;
    for (int i = 0; i < (int)ground_set.size(); i++) {
      ground_set[i].parent = -1;
    }
    int endpoint = NOT_FOUND;
    const int INF = 1e9 + 5;
    vector<pair<int, int>> dist(ground_set.size(), make_pair(INF, INF));
    for (int i = 0; i < (int)ground_set.size(); i++) {
      if (!ground_set[i].in_independent_set && graphic_matroid_oracle(i)) {
        ground_set[i].parent = SOURCE;
        dist[i] = {ground_set[i].cost, 0};
      }
    }
    vector<vector<int>> adj(ground_set.size());
    for (int i : independent_set) {
      for (int j = 0; j < (int)ground_set.size(); j++) {
        if (ground_set[j].in_independent_set) continue;
        if (graphic_matroid_oracle(j, i)) {
          adj[i].push_back(j);
        }
        if (matroid2_oracle(j, i)) {
          adj[j].push_back(i);
        }
      }
    }
    bool go = true;
    for (int rep = 0; go; rep++) {
      go = false;
      vector<pair<int, int>> ndist = dist;
      for (int i = 0; i < (int)ground_set.size(); i++) {
        for (int j : adj[i]) {
          assert(ground_set[i].in_independent_set !=
                 ground_set[j].in_independent_set);
          int c;
          if (ground_set[j].in_independent_set) {
            c = -ground_set[j].cost;
          } else {
            c = ground_set[j].cost;
          }
          if (dist[i].first != INF) {
            pair<int, int> ncost = {dist[i].first + c, dist[i].second + 1};
            if (ncost < ndist[j]) {
              go = true;
              ndist[j] = ncost;
              ground_set[j].parent = i;
            }
          }
        }
      }
      dist.swap(ndist);
      if (rep == (int)ground_set.size() - 1) assert(!go);
    }
    pair<int, int> best = {INF, INF};
    for (int i = 0; i < (int)ground_set.size(); i++) {
      if (!ground_set[i].in_independent_set && dist[i] < best &&
          matroid2_oracle(i)) {
        endpoint = i;
        best = dist[i];
      }
    }
    if (endpoint == NOT_FOUND) return false;
    do {
      ground_set[endpoint].in_independent_set ^= true;
      endpoint = ground_set[endpoint].parent;
    } while (endpoint != SOURCE);
    independent_set.clear();
    for (int i = 0; i < (int)ground_set.size(); i++) {
      if (ground_set[i].in_independent_set) {
        ground_set[i].independent_set_position = independent_set.size();
        independent_set.push_back(i);
      }
    }
    return true;
  }
  void foo() {
    int k;
    cin >> n >> k;
    vector<int> L(k);
    for (int i = 0; i < k; i++) {
      cin >> L[i];
    }
    vector<vector<int>> c(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
      for (int j = i + 1; j < n; j++) {
        cin >> c[i][j];
      }
    }
    vector<pair<int, int>> mst, all;
    for (int i = k; i < n; i++) {
      for (int j = i + 1; j < n; j++) {
        all.emplace_back(i, j);
      }
    }
    sort(all.begin(), all.end(),
         [&](const pair<int, int> &e1, const pair<int, int> &e2) {
           return c[e1.first][e1.second] < c[e2.first][e2.second];
         });
    dsu g(n);
    for (const auto &e : all) {
      if (g.unite(e.first, e.second)) {
        mst.push_back(e);
      }
    }
    const int INF = 1e9 + 5;
    int ans = INF;
    limit = vector<int>(n, INF);
    function<void(int, vector<pair<int, int>> &)> rec =
        [&](int v, const vector<pair<int, int>> &edges) {
          if (v == k) {
            vector<int> al(k);
            for (const auto &[x, y] : edges) {
              al[x]++;
              al[y]++;
            }
            for (int i = 0; i < k; i++) {
              if (al[i] > L[i]) return;
              limit[i] = L[i] - al[i];
            }
            other = edges;
            ground_set.clear();
            independent_set.clear();
            for (const auto &[x, y] : mst) {
              ground_set.emplace_back(x, y, c[x][y]);
            }
            for (int i = 0; i < k; i++) {
              for (int j = k; j < n; j++) {
                ground_set.emplace_back(i, j, c[i][j]);
              }
            }
            while (augment())
              ;
            const int cnt = edges.size() + independent_set.size();
            if (cnt == n - 1) {
              int sum = 0;
              for (const auto &[x, y] : edges) {
                sum += c[x][y];
              }
              for (int id : independent_set) {
                sum += ground_set[id].cost;
              }
              ans = min(ans, sum);
            }
            return;
          }
          const int cases = 1 << v;
          for (int m = 0; m < cases; m++) {
            dsu G(k);
            for (const auto &[x, y] : edges) {
              G.unite(x, y);
            }
            bool good = true;
            vector<pair<int, int>> ne = edges;
            for (int i = 0; i < v; i++) {
              if (!(m & (1 << i))) continue;
              if (G.find(i) == G.find(v)) {
                good = false;
                break;
              }
              ne.emplace_back(i, v);
              G.unite(i, v);
            }
            if (good) {
              rec(v + 1, ne);
            }
          }
        };
    vector<pair<int, int>> vv;
    rec(0, vv);
    cout << ans << endl;
  }
  int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    foo();
  }
  