#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
const int X = 1e6;
struct DSU {
  vector<int> link;
  DSU(int n) : link(n, -1) {}
  int Find(int x) {
    if (link[x] == -1) return x;
    return link[x] = Find(link[x]);
  }
  bool Union(int a, int b) {
    a = Find(a);
    b = Find(b);
    if (a != b) {
      link[a] = b;
      return true;
    }
    return false;
  }
};
struct Tree {
  int n;
  vector<int> a, b;
  Tree(int n, vector<int> a, vector<int> b) : n(n), a(a), b(b) {}
  vector<bool> Admits(vector<bool> sol) {
    DSU D(n);
    for (int i = 0; i < (int)sol.size(); ++i) {
      if (sol[i]) D.Union(a[i], b[i]);
    }
    vector<bool> ret(sol.size(), false);
    for (int i = 0; i < (int)sol.size(); ++i) {
      if (!sol[i] && D.Find(a[i]) != D.Find(b[i])) ret[i] = true;
    }
    return ret;
  }
};
struct Color {
  vector<int> v, a, b;
  Color(vector<int> v, vector<int> a, vector<int> b) : v(v), a(a), b(b) {}
  vector<bool> Admits(vector<bool> sol) {
    vector<int> w = v;
    for (int i = 0; i < (int)sol.size(); ++i) {
      if (sol[i]) w[a[i]] -= 1, w[b[i]] -= 1;
    }
    vector<bool> ret(sol.size(), false);
    for (int i = 0; i < (int)sol.size(); ++i) {
      if (sol[i]) continue;
      ret[i] = (w[a[i]] > 0 && w[b[i]] > 0);
    }
    return ret;
  }
};
template <typename M1>
vector<vector<bool>> Exchange(M1& M, vector<bool> sol) {
  vector<vector<bool>> ret(sol.size());
  for (int i = 0; i < (int)sol.size(); ++i) {
    if (!sol[i]) continue;
    sol[i] = 0;
    ret[i] = M.Admits(sol);
    sol[i] = 1;
  }
  return ret;
}
template <class M1, class M2>
int MatroidIntersection(vector<int> w, M1 m1, M2 m2, int req) {
  int n = w.size();
  vector<bool> sol(n, false);
  for (int i = 0; i < n; ++i)
    if (w[i] == -X) sol[i] = true;
  vector<int> q;
  while (true) {
    auto adm1 = m1.Admits(sol), adm2 = m2.Admits(sol);
    auto ex1 = Exchange(m1, sol), ex2 = Exchange(m2, sol);
    q.clear();
    vector<int> inq(n, false);
    vector<int> parent(n, -2);
    vector<int> dist(n, INF);
    vector<int> depth(n, 0);
    auto push = [&](int i, int p, int d, int d2) {
      if (d > dist[i]) return;
      if (d == dist[i] && d2 >= depth[i]) return;
      dist[i] = d;
      parent[i] = p;
      depth[i] = d2;
      if (!inq[i]) q.push_back(i), inq[i] = 1;
    };
    for (int i = 0; i < n; ++i) {
      if (abs(w[i]) == X) continue;
      if (!sol[i] && adm1[i]) {
        push(i, -1, w[i], 0);
      }
    }
    int ch = 1, iter = 0;
    for (int i = 0; i < (int)q.size(); ++i) {
      int node = q[i];
      inq[node] = 0;
      for (int vec = 0; vec < n; ++vec) {
        if (abs(w[vec]) == X) continue;
        if (sol[node] != sol[vec]) {
          assert(dist[node] != INF);
          if (sol[node]) {
            if (ex1[node][vec])
              push(vec, node, dist[node] + w[vec], depth[node] + 1);
          } else {
            if (ex2[vec][node])
              push(vec, node, dist[node] - w[vec], depth[node] + 1);
          }
        }
      }
    }
    int best = INF;
    int choose = -1;
    for (int node = 0; node < n; ++node) {
      if (abs(w[node]) == X) continue;
      if (!sol[node] && adm2[node] && parent[node] != -2) {
        auto now = dist[node];
        if (now < best) {
          best = now;
          choose = node;
        }
      }
    }
    if (choose == -1) break;
    for (int node = choose; node != -1; node = parent[node]) {
      sol[node] = !sol[node];
    }
  }
  int ans = 0, cnt = 0;
  for (int i = 0; i < n; ++i) {
    if (sol[i]) {
      ans += w[i];
      cnt += 1;
    }
  }
  if (cnt != req) return INF;
  return ans;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int n, k;
  cin >> n >> k;
  vector<int> v(n, n);
  for (int i = 0; i < k; ++i) cin >> v[i];
  vector<int> a, b, w;
  for (int i = 0; i < n; ++i) {
    for (int j = i + 1; j < n; ++j) {
      int x;
      cin >> x;
      a.push_back(i);
      b.push_back(j);
      w.push_back(x);
    }
  }
  int m = a.size();
  vector<int> o(m);
  iota(o.begin(), o.end(), 0);
  sort(o.begin(), o.end(), [&](int a, int b) { return w[a] < w[b]; });
  vector<int> na, nb, nw, si;
  DSU D(n);
  for (auto i : o) {
    if (a[i] < k && b[i] < k) si.push_back(na.size());
    if (a[i] < k || b[i] < k || D.Union(a[i], b[i])) {
      na.push_back(a[i]);
      nb.push_back(b[i]);
      nw.push_back(w[i]);
    }
  }
  a = na;
  b = nb;
  w = nw;
  int sol = INF;
  for (int msk = 0; msk < (1 << si.size()); ++msk) {
    DSU D(n);
    vector<int> now_w = w;
    vector<int> ww = v;
    int delta = 0;
    bool bad = false;
    for (int i = 0; i < (int)si.size(); ++i) {
      if (msk & (1 << i)) {
        if (!D.Union(a[si[i]], b[si[i]])) bad = true;
        if (--ww[a[si[i]]] < 0 || --ww[b[si[i]]] < 0) bad = true;
        delta += w[si[i]] + X;
        now_w[si[i]] = -X;
      } else
        now_w[si[i]] = X;
    }
    if (bad) continue;
    Tree T(n, a, b);
    Color C(v, a, b);
    auto now = MatroidIntersection(now_w, T, C, n - 1);
    sol = min(sol, now + delta);
  }
  cout << sol << endl;
  return 0;
}

### Prompt

Please provide a CPP coded solution to the problem described below:

<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

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
const int X = 1e6;
struct DSU {
  vector<int> link;
  DSU(int n) : link(n, -1) {}
  int Find(int x) {
    if (link[x] == -1) return x;
    return link[x] = Find(link[x]);
  }
  bool Union(int a, int b) {
    a = Find(a);
    b = Find(b);
    if (a != b) {
      link[a] = b;
      return true;
    }
    return false;
  }
};
struct Tree {
  int n;
  vector<int> a, b;
  Tree(int n, vector<int> a, vector<int> b) : n(n), a(a), b(b) {}
  vector<bool> Admits(vector<bool> sol) {
    DSU D(n);
    for (int i = 0; i < (int)sol.size(); ++i) {
      if (sol[i]) D.Union(a[i], b[i]);
    }
    vector<bool> ret(sol.size(), false);
    for (int i = 0; i < (int)sol.size(); ++i) {
      if (!sol[i] && D.Find(a[i]) != D.Find(b[i])) ret[i] = true;
    }
    return ret;
  }
};
struct Color {
  vector<int> v, a, b;
  Color(vector<int> v, vector<int> a, vector<int> b) : v(v), a(a), b(b) {}
  vector<bool> Admits(vector<bool> sol) {
    vector<int> w = v;
    for (int i = 0; i < (int)sol.size(); ++i) {
      if (sol[i]) w[a[i]] -= 1, w[b[i]] -= 1;
    }
    vector<bool> ret(sol.size(), false);
    for (int i = 0; i < (int)sol.size(); ++i) {
      if (sol[i]) continue;
      ret[i] = (w[a[i]] > 0 && w[b[i]] > 0);
    }
    return ret;
  }
};
template <typename M1>
vector<vector<bool>> Exchange(M1& M, vector<bool> sol) {
  vector<vector<bool>> ret(sol.size());
  for (int i = 0; i < (int)sol.size(); ++i) {
    if (!sol[i]) continue;
    sol[i] = 0;
    ret[i] = M.Admits(sol);
    sol[i] = 1;
  }
  return ret;
}
template <class M1, class M2>
int MatroidIntersection(vector<int> w, M1 m1, M2 m2, int req) {
  int n = w.size();
  vector<bool> sol(n, false);
  for (int i = 0; i < n; ++i)
    if (w[i] == -X) sol[i] = true;
  vector<int> q;
  while (true) {
    auto adm1 = m1.Admits(sol), adm2 = m2.Admits(sol);
    auto ex1 = Exchange(m1, sol), ex2 = Exchange(m2, sol);
    q.clear();
    vector<int> inq(n, false);
    vector<int> parent(n, -2);
    vector<int> dist(n, INF);
    vector<int> depth(n, 0);
    auto push = [&](int i, int p, int d, int d2) {
      if (d > dist[i]) return;
      if (d == dist[i] && d2 >= depth[i]) return;
      dist[i] = d;
      parent[i] = p;
      depth[i] = d2;
      if (!inq[i]) q.push_back(i), inq[i] = 1;
    };
    for (int i = 0; i < n; ++i) {
      if (abs(w[i]) == X) continue;
      if (!sol[i] && adm1[i]) {
        push(i, -1, w[i], 0);
      }
    }
    int ch = 1, iter = 0;
    for (int i = 0; i < (int)q.size(); ++i) {
      int node = q[i];
      inq[node] = 0;
      for (int vec = 0; vec < n; ++vec) {
        if (abs(w[vec]) == X) continue;
        if (sol[node] != sol[vec]) {
          assert(dist[node] != INF);
          if (sol[node]) {
            if (ex1[node][vec])
              push(vec, node, dist[node] + w[vec], depth[node] + 1);
          } else {
            if (ex2[vec][node])
              push(vec, node, dist[node] - w[vec], depth[node] + 1);
          }
        }
      }
    }
    int best = INF;
    int choose = -1;
    for (int node = 0; node < n; ++node) {
      if (abs(w[node]) == X) continue;
      if (!sol[node] && adm2[node] && parent[node] != -2) {
        auto now = dist[node];
        if (now < best) {
          best = now;
          choose = node;
        }
      }
    }
    if (choose == -1) break;
    for (int node = choose; node != -1; node = parent[node]) {
      sol[node] = !sol[node];
    }
  }
  int ans = 0, cnt = 0;
  for (int i = 0; i < n; ++i) {
    if (sol[i]) {
      ans += w[i];
      cnt += 1;
    }
  }
  if (cnt != req) return INF;
  return ans;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int n, k;
  cin >> n >> k;
  vector<int> v(n, n);
  for (int i = 0; i < k; ++i) cin >> v[i];
  vector<int> a, b, w;
  for (int i = 0; i < n; ++i) {
    for (int j = i + 1; j < n; ++j) {
      int x;
      cin >> x;
      a.push_back(i);
      b.push_back(j);
      w.push_back(x);
    }
  }
  int m = a.size();
  vector<int> o(m);
  iota(o.begin(), o.end(), 0);
  sort(o.begin(), o.end(), [&](int a, int b) { return w[a] < w[b]; });
  vector<int> na, nb, nw, si;
  DSU D(n);
  for (auto i : o) {
    if (a[i] < k && b[i] < k) si.push_back(na.size());
    if (a[i] < k || b[i] < k || D.Union(a[i], b[i])) {
      na.push_back(a[i]);
      nb.push_back(b[i]);
      nw.push_back(w[i]);
    }
  }
  a = na;
  b = nb;
  w = nw;
  int sol = INF;
  for (int msk = 0; msk < (1 << si.size()); ++msk) {
    DSU D(n);
    vector<int> now_w = w;
    vector<int> ww = v;
    int delta = 0;
    bool bad = false;
    for (int i = 0; i < (int)si.size(); ++i) {
      if (msk & (1 << i)) {
        if (!D.Union(a[si[i]], b[si[i]])) bad = true;
        if (--ww[a[si[i]]] < 0 || --ww[b[si[i]]] < 0) bad = true;
        delta += w[si[i]] + X;
        now_w[si[i]] = -X;
      } else
        now_w[si[i]] = X;
    }
    if (bad) continue;
    Tree T(n, a, b);
    Color C(v, a, b);
    auto now = MatroidIntersection(now_w, T, C, n - 1);
    sol = min(sol, now + delta);
  }
  cout << sol << endl;
  return 0;
}

```