#include <bits/stdc++.h>
using namespace std;
const int maxn = 55, maxm = 1250, inf = 2e9;
int n, K, m, N, D[maxn], w[maxn][maxn], id[maxn][maxn], wei[maxm];
int C[maxn], fa[maxn], dis[maxm], ce[maxm], pre[maxm];
int dd[maxm][2], ans = inf;
bool in[maxn][maxn], inq[maxm];
pair<int, int> E[maxn], F[maxn];
vector<int> G[maxm];
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
void brute(int x, int y) {
  if (x > K) {
    for (int i = int(1); i <= int(K); i++) fa[i] = i;
    for (int i = int(1); i <= int(K); i++) C[i] = 0;
    for (int i = int(1); i <= int(m); i++) {
      int x = E[i].first;
      int y = E[i].second;
      if (++C[x] > D[x]) return;
      if (++C[y] > D[y]) return;
      x = find(x);
      y = find(y);
      if (x == y) return;
      fa[x] = y;
    }
    memset(in, 0, sizeof(in));
    int s = 0;
    for (int i = int(1); i <= int(m); i++) s += w[E[i].first][E[i].second];
    while (1) {
      if (s >= ans) return;
      int r = 0;
      for (int i = int(1); i <= int(m); i++) F[i] = E[i];
      for (int i = int(1); i <= int(n); i++)
        for (int j = int(max(K, i) + 1); j <= int(n); j++)
          if (in[i][j]) F[(++r) + m] = {i, j};
      for (int i = int(1); i <= int(N); i++) G[i].clear();
      for (int i = int(m + 1); i <= int(m + r); i++) {
        iota(fa + 1, fa + n + 1, 1);
        fill(C + 1, C + n + 1, 0);
        for (int j = int(1); j <= int(m + r); j++)
          if (j != i) {
            int x = F[j].first, y = F[j].second;
            C[x]++, C[y]++, fa[find(x)] = find(y);
          }
        int I = id[F[i].first][F[i].second];
        wei[I] = -w[F[i].first][F[i].second];
        for (int i = int(1); i <= int(n); i++)
          for (int j = int(max(K, i) + 1); j <= int(n); j++)
            if (!in[i][j]) {
              if (C[i] < D[i]) G[id[i][j]].push_back(I);
              if (find(i) != find(j)) G[I].push_back(id[i][j]);
            }
      }
      for (int i = int(1); i <= int(n); i++)
        for (int j = int(max(K, i) + 1); j <= int(n); j++)
          if (!in[i][j]) {
            wei[id[i][j]] = w[i][j];
          }
      iota(fa + 1, fa + n + 1, 1);
      fill(C + 1, C + n + 1, 0);
      for (int i = int(1); i <= int(m + r); i++) {
        int x = F[i].first, y = F[i].second;
        C[x]++, C[y]++, fa[find(x)] = find(y);
      }
      for (int i = int(1); i <= int(N); i++)
        dis[i] = inf, ce[i] = 0, pre[i] = 0;
      queue<int> Q;
      for (int i = int(1); i <= int(n); i++)
        for (int j = int(max(K, i) + 1); j <= int(n); j++)
          if (!in[i][j]) {
            if (find(i) != find(j)) {
              dis[id[i][j]] = w[i][j], Q.push(id[i][j]), inq[id[i][j]] = 1;
            }
          }
      while (!Q.empty()) {
        int u = Q.front();
        Q.pop();
        for (int v : G[u])
          if (dis[v] > dis[u] + wei[v] ||
              (dis[v] == dis[u] + wei[v] && ce[v] > ce[u] + 1)) {
            pre[v] = u, dis[v] = dis[u] + wei[v], ce[v] = ce[u] + 1;
            if (!inq[v]) Q.push(v);
          }
        inq[u] = 0;
      }
      int _dis = inf, _ce = 0, x = 0;
      for (int i = int(1); i <= int(n); i++)
        for (int j = int(max(K, i) + 1); j <= int(n); j++)
          if (!in[i][j]) {
            if (C[i] < D[i] &&
                (_dis > dis[id[i][j]] ||
                 (_dis == dis[id[i][j]] && _ce > ce[id[i][j]]))) {
              x = id[i][j], _dis = dis[id[i][j]], _ce = ce[id[i][j]];
            }
          }
      if (!x) {
        if (m + r == n - 1) {
          ans = s;
        }
        return;
      }
      while (x) {
        in[dd[x][0]][dd[x][1]] ^= 1;
        s += wei[x];
        x = pre[x];
      }
    }
  }
  if (y > K) {
    brute(x + 1, x + 2);
    return;
  }
  brute(x, y + 1);
  E[++m] = {x, y}, brute(x, y + 1), --m;
}
int main() {
  scanf("%d %d", &n, &K);
  for (int i = int(1); i <= int(K); i++) {
    scanf("%d", &D[i]);
  }
  for (int i = int(K + 1); i <= int(n); i++) D[i] = n;
  for (int i = int(1); i <= int(n); i++)
    for (int j = int(i + 1); j <= int(n); j++) {
      id[i][j] = ++N;
      dd[N][0] = i, dd[N][1] = j;
      scanf("%d", &w[i][j]);
    }
  brute(1, 2);
  printf("%d\n", ans);
  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 maxn = 55, maxm = 1250, inf = 2e9;
int n, K, m, N, D[maxn], w[maxn][maxn], id[maxn][maxn], wei[maxm];
int C[maxn], fa[maxn], dis[maxm], ce[maxm], pre[maxm];
int dd[maxm][2], ans = inf;
bool in[maxn][maxn], inq[maxm];
pair<int, int> E[maxn], F[maxn];
vector<int> G[maxm];
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
void brute(int x, int y) {
  if (x > K) {
    for (int i = int(1); i <= int(K); i++) fa[i] = i;
    for (int i = int(1); i <= int(K); i++) C[i] = 0;
    for (int i = int(1); i <= int(m); i++) {
      int x = E[i].first;
      int y = E[i].second;
      if (++C[x] > D[x]) return;
      if (++C[y] > D[y]) return;
      x = find(x);
      y = find(y);
      if (x == y) return;
      fa[x] = y;
    }
    memset(in, 0, sizeof(in));
    int s = 0;
    for (int i = int(1); i <= int(m); i++) s += w[E[i].first][E[i].second];
    while (1) {
      if (s >= ans) return;
      int r = 0;
      for (int i = int(1); i <= int(m); i++) F[i] = E[i];
      for (int i = int(1); i <= int(n); i++)
        for (int j = int(max(K, i) + 1); j <= int(n); j++)
          if (in[i][j]) F[(++r) + m] = {i, j};
      for (int i = int(1); i <= int(N); i++) G[i].clear();
      for (int i = int(m + 1); i <= int(m + r); i++) {
        iota(fa + 1, fa + n + 1, 1);
        fill(C + 1, C + n + 1, 0);
        for (int j = int(1); j <= int(m + r); j++)
          if (j != i) {
            int x = F[j].first, y = F[j].second;
            C[x]++, C[y]++, fa[find(x)] = find(y);
          }
        int I = id[F[i].first][F[i].second];
        wei[I] = -w[F[i].first][F[i].second];
        for (int i = int(1); i <= int(n); i++)
          for (int j = int(max(K, i) + 1); j <= int(n); j++)
            if (!in[i][j]) {
              if (C[i] < D[i]) G[id[i][j]].push_back(I);
              if (find(i) != find(j)) G[I].push_back(id[i][j]);
            }
      }
      for (int i = int(1); i <= int(n); i++)
        for (int j = int(max(K, i) + 1); j <= int(n); j++)
          if (!in[i][j]) {
            wei[id[i][j]] = w[i][j];
          }
      iota(fa + 1, fa + n + 1, 1);
      fill(C + 1, C + n + 1, 0);
      for (int i = int(1); i <= int(m + r); i++) {
        int x = F[i].first, y = F[i].second;
        C[x]++, C[y]++, fa[find(x)] = find(y);
      }
      for (int i = int(1); i <= int(N); i++)
        dis[i] = inf, ce[i] = 0, pre[i] = 0;
      queue<int> Q;
      for (int i = int(1); i <= int(n); i++)
        for (int j = int(max(K, i) + 1); j <= int(n); j++)
          if (!in[i][j]) {
            if (find(i) != find(j)) {
              dis[id[i][j]] = w[i][j], Q.push(id[i][j]), inq[id[i][j]] = 1;
            }
          }
      while (!Q.empty()) {
        int u = Q.front();
        Q.pop();
        for (int v : G[u])
          if (dis[v] > dis[u] + wei[v] ||
              (dis[v] == dis[u] + wei[v] && ce[v] > ce[u] + 1)) {
            pre[v] = u, dis[v] = dis[u] + wei[v], ce[v] = ce[u] + 1;
            if (!inq[v]) Q.push(v);
          }
        inq[u] = 0;
      }
      int _dis = inf, _ce = 0, x = 0;
      for (int i = int(1); i <= int(n); i++)
        for (int j = int(max(K, i) + 1); j <= int(n); j++)
          if (!in[i][j]) {
            if (C[i] < D[i] &&
                (_dis > dis[id[i][j]] ||
                 (_dis == dis[id[i][j]] && _ce > ce[id[i][j]]))) {
              x = id[i][j], _dis = dis[id[i][j]], _ce = ce[id[i][j]];
            }
          }
      if (!x) {
        if (m + r == n - 1) {
          ans = s;
        }
        return;
      }
      while (x) {
        in[dd[x][0]][dd[x][1]] ^= 1;
        s += wei[x];
        x = pre[x];
      }
    }
  }
  if (y > K) {
    brute(x + 1, x + 2);
    return;
  }
  brute(x, y + 1);
  E[++m] = {x, y}, brute(x, y + 1), --m;
}
int main() {
  scanf("%d %d", &n, &K);
  for (int i = int(1); i <= int(K); i++) {
    scanf("%d", &D[i]);
  }
  for (int i = int(K + 1); i <= int(n); i++) D[i] = n;
  for (int i = int(1); i <= int(n); i++)
    for (int j = int(i + 1); j <= int(n); j++) {
      id[i][j] = ++N;
      dd[N][0] = i, dd[N][1] = j;
      scanf("%d", &w[i][j]);
    }
  brute(1, 2);
  printf("%d\n", ans);
  return 0;
}

```