#include <bits/stdc++.h>
using namespace std;
const int Inf = 0x3f3f3f3f;
mt19937_64 Rand(chrono::steady_clock::now().time_since_epoch().count());
long long inline rand(long long L, long long R) {
  return uniform_int_distribution<long long>(L, R)(Rand);
}
double inline frand() { return uniform_real_distribution<double>(0, 1)(Rand); }
struct UnionFind {
  int fa[55];
  void inline init() { memset(fa, -1, sizeof(fa)); }
  UnionFind() { init(); }
  int inline root(int x) { return fa[x] < 0 ? x : fa[x] = root(fa[x]); }
  bool inline conn(int a, int b) {
    a = root(a);
    b = root(b);
    if (a == b) return 0;
    if (fa[a] < fa[b]) swap(a, b);
    return fa[b] += fa[a], fa[a] = b, 1;
  }
} uf;
int N, K;
int d[55];
int w[55][55], deg[55], dg[55];
bool sel[55][55];
vector<tuple<int, int, int> > egs;
vector<pair<int, int> > negs;
int calc() {
  uf.init();
  int res = 0, es = 0;
  egs.clear();
  memset(deg, 0, sizeof(deg));
  for (int i = 1; i <= (N); ++i)
    for (int j = i + 1; j <= N; ++j) {
      if (sel[i][j]) {
        if (!uf.conn(i, j)) return Inf;
        res += w[i][j];
        ++deg[i];
        ++deg[j];
        ++es;
      } else
        egs.emplace_back(w[i][j], i, j);
    }
  sort(egs.begin(), egs.end());
  for (auto &e : egs) {
    int w, u, v;
    tie(w, u, v) = e;
    if (deg[u] == d[u] || deg[v] == d[v]) continue;
    if (!uf.conn(u, v)) continue;
    ++deg[u];
    ++deg[v];
    ++es;
    res += w;
  }
  if (es != N - 1) return Inf;
  return res;
}
int main() {
  scanf("%d%d", &N, &K);
  memset(d, -1, sizeof(d));
  for (int i = 1; i <= (K); ++i) scanf("%d", d + i);
  for (int i = 1; i <= (N); ++i)
    for (int j = i + 1; j <= N; ++j) scanf("%d", w[i] + j);
  for (int i = 1; i <= (K); ++i)
    for (int j = i + 1; j <= N; ++j) negs.emplace_back(i, j);
  int cur = calc(), bes = cur;
  for (double tmp = 1145.14; tmp >= 1919.8e-10; tmp *= .996007) {
    int u, v;
    while (1) {
      int id = rand(0, ((int)(negs).size()) - 1);
      tie(u, v) = negs[id];
      if (u == v) continue;
      if (u > v) swap(u, v);
      if (!sel[u][v] && (dg[u] == d[u] || dg[v] == d[v])) continue;
      break;
    }
    dg[u] -= sel[u][v];
    dg[v] -= sel[u][v];
    sel[u][v] ^= 1;
    dg[u] += sel[u][v];
    dg[v] += sel[u][v];
    int ncur = calc();
    if (exp((cur - ncur) / tmp) > frand()) {
      cur = ncur;
      bes = min(bes, cur);
    } else {
      dg[u] -= sel[u][v];
      dg[v] -= sel[u][v];
      sel[u][v] ^= 1;
      dg[u] += sel[u][v];
      dg[v] += sel[u][v];
    }
  }
  printf("%d\n", bes);
  return 0;
}

### Prompt

Please formulate 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>
using namespace std;
const int Inf = 0x3f3f3f3f;
mt19937_64 Rand(chrono::steady_clock::now().time_since_epoch().count());
long long inline rand(long long L, long long R) {
  return uniform_int_distribution<long long>(L, R)(Rand);
}
double inline frand() { return uniform_real_distribution<double>(0, 1)(Rand); }
struct UnionFind {
  int fa[55];
  void inline init() { memset(fa, -1, sizeof(fa)); }
  UnionFind() { init(); }
  int inline root(int x) { return fa[x] < 0 ? x : fa[x] = root(fa[x]); }
  bool inline conn(int a, int b) {
    a = root(a);
    b = root(b);
    if (a == b) return 0;
    if (fa[a] < fa[b]) swap(a, b);
    return fa[b] += fa[a], fa[a] = b, 1;
  }
} uf;
int N, K;
int d[55];
int w[55][55], deg[55], dg[55];
bool sel[55][55];
vector<tuple<int, int, int> > egs;
vector<pair<int, int> > negs;
int calc() {
  uf.init();
  int res = 0, es = 0;
  egs.clear();
  memset(deg, 0, sizeof(deg));
  for (int i = 1; i <= (N); ++i)
    for (int j = i + 1; j <= N; ++j) {
      if (sel[i][j]) {
        if (!uf.conn(i, j)) return Inf;
        res += w[i][j];
        ++deg[i];
        ++deg[j];
        ++es;
      } else
        egs.emplace_back(w[i][j], i, j);
    }
  sort(egs.begin(), egs.end());
  for (auto &e : egs) {
    int w, u, v;
    tie(w, u, v) = e;
    if (deg[u] == d[u] || deg[v] == d[v]) continue;
    if (!uf.conn(u, v)) continue;
    ++deg[u];
    ++deg[v];
    ++es;
    res += w;
  }
  if (es != N - 1) return Inf;
  return res;
}
int main() {
  scanf("%d%d", &N, &K);
  memset(d, -1, sizeof(d));
  for (int i = 1; i <= (K); ++i) scanf("%d", d + i);
  for (int i = 1; i <= (N); ++i)
    for (int j = i + 1; j <= N; ++j) scanf("%d", w[i] + j);
  for (int i = 1; i <= (K); ++i)
    for (int j = i + 1; j <= N; ++j) negs.emplace_back(i, j);
  int cur = calc(), bes = cur;
  for (double tmp = 1145.14; tmp >= 1919.8e-10; tmp *= .996007) {
    int u, v;
    while (1) {
      int id = rand(0, ((int)(negs).size()) - 1);
      tie(u, v) = negs[id];
      if (u == v) continue;
      if (u > v) swap(u, v);
      if (!sel[u][v] && (dg[u] == d[u] || dg[v] == d[v])) continue;
      break;
    }
    dg[u] -= sel[u][v];
    dg[v] -= sel[u][v];
    sel[u][v] ^= 1;
    dg[u] += sel[u][v];
    dg[v] += sel[u][v];
    int ncur = calc();
    if (exp((cur - ncur) / tmp) > frand()) {
      cur = ncur;
      bes = min(bes, cur);
    } else {
      dg[u] -= sel[u][v];
      dg[v] -= sel[u][v];
      sel[u][v] ^= 1;
      dg[u] += sel[u][v];
      dg[v] += sel[u][v];
    }
  }
  printf("%d\n", bes);
  return 0;
}

```