#include <bits/stdc++.h>
template <typename _Tp>
void read(_Tp &x) {
  char ch(getchar());
  bool f(false);
  while (!isdigit(ch)) f |= ch == 45, ch = getchar();
  x = ch & 15, ch = getchar();
  while (isdigit(ch)) x = x * 10 + (ch & 15), ch = getchar();
  if (f) x = -x;
}
template <typename _Tp, typename... Args>
void read(_Tp &t, Args &...args) {
  read(t);
  read(args...);
}
const int N = 55, M = N * (N - 1) / 2, inf = 0x3f3f3f3f;
struct edge {
  int v, nxt;
} c[M * M];
int front[M], ec;
inline void addedge(int u, int v) {
  c[++ec] = (edge){v, front[u]}, front[u] = ec;
}
int d[N], _w[N][N], n, k, u[M], v[M], w[M], m;
struct DSU {
  int fa[N];
  DSU() { std::iota(fa, fa + N, 0); }
  int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }
  inline void merge(int x, int y) { fa[find(x)] = find(y); }
} T, o;
std::pair<int, int> qaq[15];
int pos;
bool in[M], inq[M];
int DG[6], dg[N], a[M], _q[1000005], pre[M];
int dis[M], len[M];
int _l, _r;
bool extend() {
  memcpy(dg, DG, 24), o = T;
  ec = 0;
  for (int i = 1; i <= m; ++i)
    pre[i] = 0, dis[i] = inf, len[i] = inf, a[i] = in[i] ? -w[i] : w[i],
    front[i] = 0;
  for (int i = 1; i <= m; ++i)
    if (in[i]) {
      ++dg[u[i]], ++dg[v[i]];
      o.merge(u[i], v[i]);
    }
  _l = 1, _r = 0;
  for (int i = 1; i <= m; ++i)
    if (!in[i] && o.find(u[i]) != o.find(v[i]))
      _q[++_r] = i, dis[i] = a[i], len[i] = 0, inq[i] = true;
  for (int i = 1; i <= m; ++i)
    if (in[i]) {
      o = T;
      for (int p = 1; p <= m; ++p)
        if (in[p] && i != p) o.merge(u[p], v[p]);
      for (int p = 1; p <= m; ++p)
        if (!in[p] && o.find(u[p]) != o.find(v[p])) addedge(i, p);
    }
  for (int i = 1; i <= m; ++i)
    if (in[i]) {
      --dg[u[i]], --dg[v[i]];
      for (int p = 1; p <= m; ++p)
        if (!in[p]) {
          if (dg[u[p]] + 1 <= d[u[p]] && dg[v[p]] + 1 <= d[v[p]]) addedge(p, i);
        }
      ++dg[u[i]], ++dg[v[i]];
    }
  while (_l != _r + 1) {
    int x = _q[_l++];
    inq[x] = false;
    for (int _ = front[x]; _; _ = c[_].nxt) {
      int v = c[_].v, d = dis[x] + a[v], l = len[x] + 1;
      if (dis[v] > d || (dis[v] == d && len[v] > l)) {
        dis[v] = d, len[v] = l, pre[v] = x;
        if (!inq[v]) _q[++_r] = v, inq[v] = 1;
      }
    }
  }
  int mn1 = inf, mn2 = inf, a = 0;
  for (int i = 1; i <= m; ++i)
    if (!in[i]) {
      bool flag = (dg[u[i]] + 1 <= d[u[i]]) && (dg[v[i]] + 1 <= d[v[i]]);
      if (flag && (dis[i] < mn1 || (dis[i] == mn1 && len[i] < mn2)))
        mn1 = dis[i], mn2 = len[i], a = i;
    }
  if (a) {
    while (a) in[a] ^= 1, a = pre[a];
    return true;
  }
  return false;
}
int main() {
  read(n, k);
  memset(d, 63, sizeof(d));
  for (int i = 1; i <= k; ++i) read(d[i]);
  for (int i = 1; i <= n; ++i)
    for (int j = i + 1; j <= n; ++j) read(_w[i][j]);
  for (int i = 1; i <= n; ++i)
    for (int j = i + 1; j <= n; ++j)
      if (j > k) u[++m] = i, v[m] = j, w[m] = _w[i][j];
  for (int i = 1; i <= k; ++i)
    for (int j = i + 1; j <= k; ++j) qaq[pos++] = {i, j};
  int ans = 1e9;
  for (int st = 0; st < 1 << pos; ++st) {
    T = DSU();
    std::vector<std::pair<int, int> > E;
    for (int i = 0; i < pos; ++i)
      if (st >> i & 1) E.push_back(qaq[i]);
    memset(DG, 0, 24), memset(in, 0, sizeof(in));
    int cnt = 0, s = 0;
    bool flag = 0;
    for (auto [x, y] : E) {
      s += _w[x][y], ++cnt;
      if (T.find(x) == T.find(y)) flag = 1;
      T.merge(x, y), ++DG[x], ++DG[y];
    }
    for (int i = 1; i <= k; ++i)
      if (DG[i] > d[i]) flag = 1;
    if (flag) continue;
    while (extend()) ++cnt;
    if (cnt == n - 1) {
      for (int i = 1; i <= m; ++i)
        if (in[i]) s += w[i];
      ans = std::min(ans, s);
    }
  }
  printf("%d\n", ans);
  return 0;
}

### Prompt

Develop a solution in cpp 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>
template <typename _Tp>
void read(_Tp &x) {
  char ch(getchar());
  bool f(false);
  while (!isdigit(ch)) f |= ch == 45, ch = getchar();
  x = ch & 15, ch = getchar();
  while (isdigit(ch)) x = x * 10 + (ch & 15), ch = getchar();
  if (f) x = -x;
}
template <typename _Tp, typename... Args>
void read(_Tp &t, Args &...args) {
  read(t);
  read(args...);
}
const int N = 55, M = N * (N - 1) / 2, inf = 0x3f3f3f3f;
struct edge {
  int v, nxt;
} c[M * M];
int front[M], ec;
inline void addedge(int u, int v) {
  c[++ec] = (edge){v, front[u]}, front[u] = ec;
}
int d[N], _w[N][N], n, k, u[M], v[M], w[M], m;
struct DSU {
  int fa[N];
  DSU() { std::iota(fa, fa + N, 0); }
  int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }
  inline void merge(int x, int y) { fa[find(x)] = find(y); }
} T, o;
std::pair<int, int> qaq[15];
int pos;
bool in[M], inq[M];
int DG[6], dg[N], a[M], _q[1000005], pre[M];
int dis[M], len[M];
int _l, _r;
bool extend() {
  memcpy(dg, DG, 24), o = T;
  ec = 0;
  for (int i = 1; i <= m; ++i)
    pre[i] = 0, dis[i] = inf, len[i] = inf, a[i] = in[i] ? -w[i] : w[i],
    front[i] = 0;
  for (int i = 1; i <= m; ++i)
    if (in[i]) {
      ++dg[u[i]], ++dg[v[i]];
      o.merge(u[i], v[i]);
    }
  _l = 1, _r = 0;
  for (int i = 1; i <= m; ++i)
    if (!in[i] && o.find(u[i]) != o.find(v[i]))
      _q[++_r] = i, dis[i] = a[i], len[i] = 0, inq[i] = true;
  for (int i = 1; i <= m; ++i)
    if (in[i]) {
      o = T;
      for (int p = 1; p <= m; ++p)
        if (in[p] && i != p) o.merge(u[p], v[p]);
      for (int p = 1; p <= m; ++p)
        if (!in[p] && o.find(u[p]) != o.find(v[p])) addedge(i, p);
    }
  for (int i = 1; i <= m; ++i)
    if (in[i]) {
      --dg[u[i]], --dg[v[i]];
      for (int p = 1; p <= m; ++p)
        if (!in[p]) {
          if (dg[u[p]] + 1 <= d[u[p]] && dg[v[p]] + 1 <= d[v[p]]) addedge(p, i);
        }
      ++dg[u[i]], ++dg[v[i]];
    }
  while (_l != _r + 1) {
    int x = _q[_l++];
    inq[x] = false;
    for (int _ = front[x]; _; _ = c[_].nxt) {
      int v = c[_].v, d = dis[x] + a[v], l = len[x] + 1;
      if (dis[v] > d || (dis[v] == d && len[v] > l)) {
        dis[v] = d, len[v] = l, pre[v] = x;
        if (!inq[v]) _q[++_r] = v, inq[v] = 1;
      }
    }
  }
  int mn1 = inf, mn2 = inf, a = 0;
  for (int i = 1; i <= m; ++i)
    if (!in[i]) {
      bool flag = (dg[u[i]] + 1 <= d[u[i]]) && (dg[v[i]] + 1 <= d[v[i]]);
      if (flag && (dis[i] < mn1 || (dis[i] == mn1 && len[i] < mn2)))
        mn1 = dis[i], mn2 = len[i], a = i;
    }
  if (a) {
    while (a) in[a] ^= 1, a = pre[a];
    return true;
  }
  return false;
}
int main() {
  read(n, k);
  memset(d, 63, sizeof(d));
  for (int i = 1; i <= k; ++i) read(d[i]);
  for (int i = 1; i <= n; ++i)
    for (int j = i + 1; j <= n; ++j) read(_w[i][j]);
  for (int i = 1; i <= n; ++i)
    for (int j = i + 1; j <= n; ++j)
      if (j > k) u[++m] = i, v[m] = j, w[m] = _w[i][j];
  for (int i = 1; i <= k; ++i)
    for (int j = i + 1; j <= k; ++j) qaq[pos++] = {i, j};
  int ans = 1e9;
  for (int st = 0; st < 1 << pos; ++st) {
    T = DSU();
    std::vector<std::pair<int, int> > E;
    for (int i = 0; i < pos; ++i)
      if (st >> i & 1) E.push_back(qaq[i]);
    memset(DG, 0, 24), memset(in, 0, sizeof(in));
    int cnt = 0, s = 0;
    bool flag = 0;
    for (auto [x, y] : E) {
      s += _w[x][y], ++cnt;
      if (T.find(x) == T.find(y)) flag = 1;
      T.merge(x, y), ++DG[x], ++DG[y];
    }
    for (int i = 1; i <= k; ++i)
      if (DG[i] > d[i]) flag = 1;
    if (flag) continue;
    while (extend()) ++cnt;
    if (cnt == n - 1) {
      for (int i = 1; i <= m; ++i)
        if (in[i]) s += w[i];
      ans = std::min(ans, s);
    }
  }
  printf("%d\n", ans);
  return 0;
}

```