#include <bits/stdc++.h>
using namespace std;
const int INFi = 1e9 + 5;
const int md = 1e9 + 7;
const long long INF = 2e18;
const int maxN = 5e5 + 1;
double getTime() { return clock() / (double)CLOCKS_PER_SEC; }
inline int add(const int &a, const int &b) {
  return a + b >= md ? a + b - md : a + b;
}
inline int sub(const int &a, const int &b) {
  return a - b < 0 ? a - b + md : a - b;
}
inline int mul(const int &a, const int &b) { return (1ll * a * b) % md; }
int binpow(int a, int b) {
  if (b <= 0) return 1;
  if (b % 2) return mul(a, binpow(a, b - 1));
  int m = binpow(a, b / 2);
  return mul(m, m);
}
int rev(int a) { return binpow(a, md - 2); }
int n, k;
vector<int> d;
vector<vector<double>> g;
vector<int> deg;
double last = 0;
void solve1() {
  last = 0;
  deg.assign(n, 0);
  vector<bool> was(n);
  vector<double> mn(n, INF);
  vector<int> fr(n, -1);
  mn[0] = 0;
  for (int _ = 0; _ < (n); ++_) {
    int x = -1;
    for (int j = 0; j < (n); ++j) {
      if (was[j]) continue;
      if (mn[j] < mn[x] || x == -1) {
        x = j;
        continue;
      }
      if (mn[j] == mn[x] && fr[j] >= k && j >= k) {
        x = j;
      }
    }
    if (fr[x] != -1) {
      deg[x]++;
      deg[fr[x]]++;
    }
    last += mn[x];
    was[x] = true;
    for (int j = 0; j < (n); ++j) {
      if (was[j]) continue;
      if (mn[j] > g[x][j]) {
        mn[j] = g[x][j];
        fr[j] = x;
      } else if (mn[j] == g[x][j] && x >= k) {
        fr[j] = x;
      }
    }
  }
}
int K = 10;
bool need = false;
void go(int i) {
  if (i == k) {
    solve1();
    return;
  }
  double l = 0, r = 110;
  for (int _ = 0; _ < (K); ++_) {
    double mid = (r + l) / 2;
    for (int j = 0; j < (n); ++j) {
      g[i][j] += mid;
      g[j][i] += mid;
    }
    go(i + 1);
    for (int j = 0; j < (n); ++j) {
      g[i][j] -= mid;
      g[j][i] -= mid;
    }
    if (deg[i] < d[i]) {
      r = mid;
    } else {
      l = mid;
    }
  }
  if (need) r = l;
  for (int j = 0; j < (n); ++j) {
    g[i][j] += r;
    g[j][i] += r;
  }
  go(i + 1);
  for (int j = 0; j < (n); ++j) {
    g[i][j] -= r;
    g[j][i] -= r;
  }
  last -= deg[i] * r;
}
void solve() {
  cin >> n >> k;
  d.resize(k);
  for (int i = 0; i < (k); ++i) cin >> d[i];
  g.resize(n, vector<double>(n));
  vector<int> ord(n);
  vector<long long> d2(n, n);
  for (int i = 0; i < (k); ++i) d2[i] = d[i];
  iota((ord).begin(), (ord).end(), 0ll);
  sort((ord).begin(), (ord).end(), [&](const int &i, const int &j) {
    return make_pair(d2[i], i) < make_pair(d2[j], j);
  });
  mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  for (int l = 0, r = 0; l < n; l = r) {
    while (r < n && d2[ord[r]] == d2[ord[l]]) r++;
    if (l < k) r = min(r, k);
  }
  vector<int> pos(n);
  for (int i = 0; i < (n); ++i) pos[ord[i]] = i;
  for (int i = 0; i < (n); ++i) {
    for (int j = i + 1; j < n; ++j) {
      cin >> g[pos[i]][pos[j]];
      g[pos[j]][pos[i]] = g[pos[i]][pos[j]];
    }
  }
  for (int i = 0; i < (k); ++i) d[i] = d2[ord[i]];
  need = true;
  go(0);
  for (int i = 0; i < (k); ++i) d[i]++;
  need = false;
  double L = last;
  go(0);
  double R = last;
  cout << round((R + L) / 2) << '\n';
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int tests = 1;
  for (int _ = 0; _ < (tests); ++_) {
    solve();
  }
  return 0;
}

### 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>
using namespace std;
const int INFi = 1e9 + 5;
const int md = 1e9 + 7;
const long long INF = 2e18;
const int maxN = 5e5 + 1;
double getTime() { return clock() / (double)CLOCKS_PER_SEC; }
inline int add(const int &a, const int &b) {
  return a + b >= md ? a + b - md : a + b;
}
inline int sub(const int &a, const int &b) {
  return a - b < 0 ? a - b + md : a - b;
}
inline int mul(const int &a, const int &b) { return (1ll * a * b) % md; }
int binpow(int a, int b) {
  if (b <= 0) return 1;
  if (b % 2) return mul(a, binpow(a, b - 1));
  int m = binpow(a, b / 2);
  return mul(m, m);
}
int rev(int a) { return binpow(a, md - 2); }
int n, k;
vector<int> d;
vector<vector<double>> g;
vector<int> deg;
double last = 0;
void solve1() {
  last = 0;
  deg.assign(n, 0);
  vector<bool> was(n);
  vector<double> mn(n, INF);
  vector<int> fr(n, -1);
  mn[0] = 0;
  for (int _ = 0; _ < (n); ++_) {
    int x = -1;
    for (int j = 0; j < (n); ++j) {
      if (was[j]) continue;
      if (mn[j] < mn[x] || x == -1) {
        x = j;
        continue;
      }
      if (mn[j] == mn[x] && fr[j] >= k && j >= k) {
        x = j;
      }
    }
    if (fr[x] != -1) {
      deg[x]++;
      deg[fr[x]]++;
    }
    last += mn[x];
    was[x] = true;
    for (int j = 0; j < (n); ++j) {
      if (was[j]) continue;
      if (mn[j] > g[x][j]) {
        mn[j] = g[x][j];
        fr[j] = x;
      } else if (mn[j] == g[x][j] && x >= k) {
        fr[j] = x;
      }
    }
  }
}
int K = 10;
bool need = false;
void go(int i) {
  if (i == k) {
    solve1();
    return;
  }
  double l = 0, r = 110;
  for (int _ = 0; _ < (K); ++_) {
    double mid = (r + l) / 2;
    for (int j = 0; j < (n); ++j) {
      g[i][j] += mid;
      g[j][i] += mid;
    }
    go(i + 1);
    for (int j = 0; j < (n); ++j) {
      g[i][j] -= mid;
      g[j][i] -= mid;
    }
    if (deg[i] < d[i]) {
      r = mid;
    } else {
      l = mid;
    }
  }
  if (need) r = l;
  for (int j = 0; j < (n); ++j) {
    g[i][j] += r;
    g[j][i] += r;
  }
  go(i + 1);
  for (int j = 0; j < (n); ++j) {
    g[i][j] -= r;
    g[j][i] -= r;
  }
  last -= deg[i] * r;
}
void solve() {
  cin >> n >> k;
  d.resize(k);
  for (int i = 0; i < (k); ++i) cin >> d[i];
  g.resize(n, vector<double>(n));
  vector<int> ord(n);
  vector<long long> d2(n, n);
  for (int i = 0; i < (k); ++i) d2[i] = d[i];
  iota((ord).begin(), (ord).end(), 0ll);
  sort((ord).begin(), (ord).end(), [&](const int &i, const int &j) {
    return make_pair(d2[i], i) < make_pair(d2[j], j);
  });
  mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  for (int l = 0, r = 0; l < n; l = r) {
    while (r < n && d2[ord[r]] == d2[ord[l]]) r++;
    if (l < k) r = min(r, k);
  }
  vector<int> pos(n);
  for (int i = 0; i < (n); ++i) pos[ord[i]] = i;
  for (int i = 0; i < (n); ++i) {
    for (int j = i + 1; j < n; ++j) {
      cin >> g[pos[i]][pos[j]];
      g[pos[j]][pos[i]] = g[pos[i]][pos[j]];
    }
  }
  for (int i = 0; i < (k); ++i) d[i] = d2[ord[i]];
  need = true;
  go(0);
  for (int i = 0; i < (k); ++i) d[i]++;
  need = false;
  double L = last;
  go(0);
  double R = last;
  cout << round((R + L) / 2) << '\n';
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int tests = 1;
  for (int _ = 0; _ < (tests); ++_) {
    solve();
  }
  return 0;
}

```