#include <bits/stdc++.h>
template <typename T>
bool chkmax(T &x, T y) {
  return x < y ? x = y, true : false;
}
template <typename T>
bool chkmin(T &x, T y) {
  return x > y ? x = y, true : false;
}
using namespace std;
long long ksm(long long a, long long b) {
  if (!b) return 1;
  long long ns = ksm(a, b >> 1);
  ns = ns * ns % 1000000007;
  if (b & 1) ns = ns * a % 1000000007;
  return ns;
}
int n, m, k, N, deg[55], d[55][55], par[55];
vector<array<int, 3>> E, e, e2;
int findPar(int x) {
  if (par[x] == x)
    return x;
  else
    return par[x] = findPar(par[x]);
}
int matroid_intersection(int n, vector<array<int, 3>> w,
                         vector<array<int, 3>> w2) {
  vector<bool> used(n);
  for (auto &x : w) x[0] = -x[0];
  for (auto &x : w2) x[0] = -x[0];
  int m = w2.size();
  auto find_path = [&]() {
    vector<vector<int>> g(n + 2);
    for (int j = 0; j < n; ++j)
      if (used[j]) {
        vector<int> cdeg(N, 0);
        used[j] = false;
        for (int i = 0; i < N; i++) par[i] = i;
        for (int i = 0; i < n; i++)
          if (used[i]) {
            int u = w[i][1], v = w[i][2];
            cdeg[u]++, cdeg[v]++;
            par[findPar(u)] = findPar(v);
          }
        for (int i = 0; i < m; i++) {
          int u = w2[i][1], v = w2[i][2];
          cdeg[u]++, cdeg[v]++;
          par[findPar(u)] = findPar(v);
        }
        for (int i = 0; i < n; ++i)
          if (!used[i] && i != j) {
            int u = w[i][1], v = w[i][2];
            cdeg[u] += 1;
            cdeg[v] += 1;
            bool w = true;
            for (int r = 0; r < k; r++) w &= cdeg[r] <= deg[r];
            cdeg[u] -= 1;
            cdeg[v] -= 1;
            if (w) g[i].push_back(j);
            if (findPar(u) != findPar(v)) g[j].push_back(i);
          }
        used[j] = true;
      }
    vector<int> cdeg(N, 0);
    for (int i = 0; i < N; i++) par[i] = i;
    for (int i = 0; i < n; i++)
      if (used[i]) {
        int u = w[i][1], v = w[i][2];
        cdeg[u]++, cdeg[v]++;
        par[findPar(u)] = findPar(v);
      }
    for (int i = 0; i < m; i++) {
      int u = w2[i][1], v = w2[i][2];
      cdeg[u]++, cdeg[v]++;
      par[findPar(u)] = findPar(v);
    }
    for (int i = 0; i < n; ++i)
      if (!used[i]) {
        int u = w[i][1], v = w[i][2];
        cdeg[u] += 1;
        cdeg[v] += 1;
        bool w = true;
        for (int r = 0; r < k; r++) w &= cdeg[r] <= deg[r];
        cdeg[u] -= 1;
        cdeg[v] -= 1;
        if (w) g[i].push_back(n + 1);
        if (findPar(u) != findPar(v)) g[n].push_back(i);
      }
    const int INF = 1 << 29;
    vector<int> dist(n + 2, INF);
    vector<bool> vis(n + 2);
    vector<int> pre(n + 2, -1);
    queue<int> q;
    dist[n] = 0;
    q.push(n);
    while (!q.empty()) {
      int x = q.front();
      q.pop();
      vis[x] = false;
      for (int y : g[x]) {
        int cost = 0;
        if (y < n) cost = used[y] ? w[y][0] : -w[y][0];
        if (dist[y] > dist[x] + cost) {
          dist[y] = dist[x] + cost;
          pre[y] = x;
          if (!vis[y]) vis[y] = true, q.push(y);
        }
      }
    }
    if (dist[n + 1] == INF) return false;
    for (int i = pre[n + 1]; i != n; i = pre[i]) {
      used[i] = !used[i];
    }
    return true;
  };
  int z = 0;
  while (find_path()) ++z;
  int res = 0;
  for (int i = 0; i < n; ++i)
    if (used[i]) res += w[i][0];
  for (auto x : w2) res += x[0], z += 1;
  if (z != N - 1) return -(1 << 29);
  return res;
}
int main() {
  scanf("%d%d", &n, &k);
  N = n;
  for (int i = 0; i < k; i++) {
    scanf("%d", deg + i);
  }
  for (int i = 0; i < n; i++)
    for (int j = i + 1; j < n; j++) {
      scanf("%d", &d[i][j]);
      if (j < k) {
        e2.push_back({d[i][j], i, j});
      } else if (i < k && j >= k)
        e.push_back({d[i][j], i, j});
      else {
        E.push_back({d[i][j], i, j});
      }
    }
  sort(E.begin(), E.end());
  for (int i = 0; i < n; i++) {
    par[i] = i;
  }
  for (auto x : E) {
    int u = x[1], v = x[2];
    if (findPar(u) != findPar(v)) {
      par[findPar(v)] = findPar(u);
      e.push_back(x);
    }
  }
  int ans = 1 << 29;
  int m = e2.size();
  for (int s = 0; s < (1 << m); s++) {
    for (int i = 0; i < k; i++) {
      par[i] = i;
    }
    bool ww = true;
    vector<array<int, 3>> e3;
    int d = 0;
    for (int j = 0; j < m; j++)
      if (s & (1 << j)) {
        int u = e2[j][1], v = e2[j][2];
        if (findPar(u) == findPar(v)) {
          ww = false;
          break;
        }
        e3.push_back(e2[j]);
        par[findPar(v)] = findPar(u);
      }
    if (!ww) continue;
    int w = -matroid_intersection(e.size(), e, e3);
    if (w >= (1 << 29)) continue;
    ans = min(ans, w);
  }
  printf("%d\n", ans);
}

### Prompt

Your challenge is to write a CPP solution to the following problem:

<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>
template <typename T>
bool chkmax(T &x, T y) {
  return x < y ? x = y, true : false;
}
template <typename T>
bool chkmin(T &x, T y) {
  return x > y ? x = y, true : false;
}
using namespace std;
long long ksm(long long a, long long b) {
  if (!b) return 1;
  long long ns = ksm(a, b >> 1);
  ns = ns * ns % 1000000007;
  if (b & 1) ns = ns * a % 1000000007;
  return ns;
}
int n, m, k, N, deg[55], d[55][55], par[55];
vector<array<int, 3>> E, e, e2;
int findPar(int x) {
  if (par[x] == x)
    return x;
  else
    return par[x] = findPar(par[x]);
}
int matroid_intersection(int n, vector<array<int, 3>> w,
                         vector<array<int, 3>> w2) {
  vector<bool> used(n);
  for (auto &x : w) x[0] = -x[0];
  for (auto &x : w2) x[0] = -x[0];
  int m = w2.size();
  auto find_path = [&]() {
    vector<vector<int>> g(n + 2);
    for (int j = 0; j < n; ++j)
      if (used[j]) {
        vector<int> cdeg(N, 0);
        used[j] = false;
        for (int i = 0; i < N; i++) par[i] = i;
        for (int i = 0; i < n; i++)
          if (used[i]) {
            int u = w[i][1], v = w[i][2];
            cdeg[u]++, cdeg[v]++;
            par[findPar(u)] = findPar(v);
          }
        for (int i = 0; i < m; i++) {
          int u = w2[i][1], v = w2[i][2];
          cdeg[u]++, cdeg[v]++;
          par[findPar(u)] = findPar(v);
        }
        for (int i = 0; i < n; ++i)
          if (!used[i] && i != j) {
            int u = w[i][1], v = w[i][2];
            cdeg[u] += 1;
            cdeg[v] += 1;
            bool w = true;
            for (int r = 0; r < k; r++) w &= cdeg[r] <= deg[r];
            cdeg[u] -= 1;
            cdeg[v] -= 1;
            if (w) g[i].push_back(j);
            if (findPar(u) != findPar(v)) g[j].push_back(i);
          }
        used[j] = true;
      }
    vector<int> cdeg(N, 0);
    for (int i = 0; i < N; i++) par[i] = i;
    for (int i = 0; i < n; i++)
      if (used[i]) {
        int u = w[i][1], v = w[i][2];
        cdeg[u]++, cdeg[v]++;
        par[findPar(u)] = findPar(v);
      }
    for (int i = 0; i < m; i++) {
      int u = w2[i][1], v = w2[i][2];
      cdeg[u]++, cdeg[v]++;
      par[findPar(u)] = findPar(v);
    }
    for (int i = 0; i < n; ++i)
      if (!used[i]) {
        int u = w[i][1], v = w[i][2];
        cdeg[u] += 1;
        cdeg[v] += 1;
        bool w = true;
        for (int r = 0; r < k; r++) w &= cdeg[r] <= deg[r];
        cdeg[u] -= 1;
        cdeg[v] -= 1;
        if (w) g[i].push_back(n + 1);
        if (findPar(u) != findPar(v)) g[n].push_back(i);
      }
    const int INF = 1 << 29;
    vector<int> dist(n + 2, INF);
    vector<bool> vis(n + 2);
    vector<int> pre(n + 2, -1);
    queue<int> q;
    dist[n] = 0;
    q.push(n);
    while (!q.empty()) {
      int x = q.front();
      q.pop();
      vis[x] = false;
      for (int y : g[x]) {
        int cost = 0;
        if (y < n) cost = used[y] ? w[y][0] : -w[y][0];
        if (dist[y] > dist[x] + cost) {
          dist[y] = dist[x] + cost;
          pre[y] = x;
          if (!vis[y]) vis[y] = true, q.push(y);
        }
      }
    }
    if (dist[n + 1] == INF) return false;
    for (int i = pre[n + 1]; i != n; i = pre[i]) {
      used[i] = !used[i];
    }
    return true;
  };
  int z = 0;
  while (find_path()) ++z;
  int res = 0;
  for (int i = 0; i < n; ++i)
    if (used[i]) res += w[i][0];
  for (auto x : w2) res += x[0], z += 1;
  if (z != N - 1) return -(1 << 29);
  return res;
}
int main() {
  scanf("%d%d", &n, &k);
  N = n;
  for (int i = 0; i < k; i++) {
    scanf("%d", deg + i);
  }
  for (int i = 0; i < n; i++)
    for (int j = i + 1; j < n; j++) {
      scanf("%d", &d[i][j]);
      if (j < k) {
        e2.push_back({d[i][j], i, j});
      } else if (i < k && j >= k)
        e.push_back({d[i][j], i, j});
      else {
        E.push_back({d[i][j], i, j});
      }
    }
  sort(E.begin(), E.end());
  for (int i = 0; i < n; i++) {
    par[i] = i;
  }
  for (auto x : E) {
    int u = x[1], v = x[2];
    if (findPar(u) != findPar(v)) {
      par[findPar(v)] = findPar(u);
      e.push_back(x);
    }
  }
  int ans = 1 << 29;
  int m = e2.size();
  for (int s = 0; s < (1 << m); s++) {
    for (int i = 0; i < k; i++) {
      par[i] = i;
    }
    bool ww = true;
    vector<array<int, 3>> e3;
    int d = 0;
    for (int j = 0; j < m; j++)
      if (s & (1 << j)) {
        int u = e2[j][1], v = e2[j][2];
        if (findPar(u) == findPar(v)) {
          ww = false;
          break;
        }
        e3.push_back(e2[j]);
        par[findPar(v)] = findPar(u);
      }
    if (!ww) continue;
    int w = -matroid_intersection(e.size(), e, e3);
    if (w >= (1 << 29)) continue;
    ans = min(ans, w);
  }
  printf("%d\n", ans);
}

```