#include <bits/stdc++.h>
const int mod = 1000000007;
const int gmod = 3;
const int inf = 1039074182;
const double eps = 1e-9;
const double pi = 3.141592653589793238462643383279;
const long long llinf = 2LL * inf * inf;
template <typename T1, typename T2>
inline void chmin(T1 &x, T2 b) {
  if (b < x) x = b;
}
template <typename T1, typename T2>
inline void chmax(T1 &x, T2 b) {
  if (b > x) x = b;
}
inline void chadd(int &x, int b) {
  x += b - mod;
  x += (x >> 31 & mod);
}
template <typename T1, typename T2>
inline void chadd(T1 &x, T2 b) {
  x += b;
  if (x >= mod) x -= mod;
}
template <typename T1, typename T2>
inline void chmul(T1 &x, T2 b) {
  x = 1LL * x * b % mod;
}
template <typename T1, typename T2>
inline void chmod(T1 &x, T2 b) {
  x %= b, x += b;
  if (x >= b) x -= b;
}
template <typename T>
inline T mabs(T x) {
  return (x < 0 ? -x : x);
}
using namespace std;
using namespace std;
template <typename T>
ostream &operator<<(ostream &cout, const vector<T> &vec) {
  cout << "{";
  for (int i = 0; i < (int)vec.size(); i++) {
    cout << vec[i];
    if (i != (int)vec.size() - 1) cout << ',';
  }
  cout << "}";
  return cout;
}
template <typename T1, typename T2>
ostream &operator<<(ostream &cout, pair<T1, T2> p) {
  cout << "(" << p.first << ',' << p.second << ")";
  return cout;
}
template <typename T, typename T2>
ostream &operator<<(ostream &cout, set<T, T2> s) {
  vector<T> t;
  for (auto x : s) t.push_back(x);
  cout << t;
  return cout;
}
template <typename T, typename T2>
ostream &operator<<(ostream &cout, multiset<T, T2> s) {
  vector<T> t;
  for (auto x : s) t.push_back(x);
  cout << t;
  return cout;
}
template <typename T>
ostream &operator<<(ostream &cout, queue<T> q) {
  vector<T> t;
  while (q.size()) {
    t.push_back(q.front());
    q.pop();
  }
  cout << t;
  return cout;
}
template <typename T1, typename T2, typename T3>
ostream &operator<<(ostream &cout, map<T1, T2, T3> m) {
  for (auto &x : m) {
    cout << "Key: " << x.first << ' ' << "Value: " << x.second << endl;
  }
  return cout;
}
template <typename T1, typename T2>
void operator+=(pair<T1, T2> &x, const pair<T1, T2> y) {
  x.first += y.first;
  x.second += y.second;
}
template <typename T1, typename T2>
pair<T1, T2> operator+(const pair<T1, T2> &x, const pair<T1, T2> &y) {
  return make_pair(x.first + y.first, x.second + y.second);
}
template <typename T1, typename T2>
pair<T1, T2> operator-(const pair<T1, T2> &x, const pair<T1, T2> &y) {
  return make_pair(x.first - y.first, x.second - y.second);
}
template <typename T1, typename T2>
pair<T1, T2> operator-(pair<T1, T2> x) {
  return make_pair(-x.first, -x.second);
}
template <typename T>
vector<vector<T>> operator~(vector<vector<T>> vec) {
  vector<vector<T>> v;
  int n = vec.size(), m = vec[0].size();
  v.resize(m);
  for (int i = 0; i < m; i++) {
    v[i].resize(n);
  }
  for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
      v[i][j] = vec[j][i];
    }
  }
  return v;
}
void print0x(int x) {
  std::vector<int> vec;
  while (x) {
    vec.push_back(x & 1);
    x >>= 1;
  }
  std::reverse(vec.begin(), vec.end());
  for (int i = 0; i < (int)vec.size(); i++) {
    std::cout << vec[i];
  }
  std::cout << ' ';
}
template <typename T>
void print0x(T x, int len) {
  std::vector<int> vec;
  while (x) {
    std::cout << (x & 1);
    x >>= 1;
    len--;
  }
  while (len--) cout << 0;
}
vector<string> vec_splitter(string s) {
  s += ',';
  vector<string> res;
  while (!s.empty()) {
    res.push_back(s.substr(0, s.find(',')));
    s = s.substr(s.find(',') + 1);
  }
  return res;
}
void debug_out(vector<string> __attribute__((unused)) args,
               __attribute__((unused)) int idx,
               __attribute__((unused)) int LINE_NUM) {
  cerr << endl;
}
template <typename Head, typename... Tail>
void debug_out(vector<string> args, int idx, int LINE_NUM, Head H, Tail... T) {
  if (idx > 0)
    cerr << ", ";
  else
    cerr << "Line(" << LINE_NUM << ") ";
  stringstream ss;
  ss << H;
  cerr << args[idx] << " = " << ss.str();
  debug_out(args, idx + 1, LINE_NUM, T...);
}
struct DSUAE {
  int *f;
  inline void clear(int n) {
    for (int i = 0; i < n; i++) {
      f[i] = i;
    }
  }
  inline void init(int n) {
    f = new int[n + 5];
    clear(n);
  }
  inline int find(int x) { return (f[x] == x ? x : f[x] = find(f[x])); }
  inline bool merge(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) return 0;
    if (x & 1)
      f[x] = y;
    else
      f[y] = x;
    return 1;
  }
  inline bool same(int x, int y) { return (find(x) == find(y)); }
};
struct DSU {
  int *f;
  int *depth;
  int *sz;
  int n;
  inline void clear(int n) {
    for (int i = 0; i < n; i++) {
      f[i] = i;
      depth[i] = 1;
      sz[i] = 1;
    }
  }
  inline void init(int _n) {
    n = _n;
    f = new int[n + 5];
    depth = new int[n + 5];
    sz = new int[n + 5];
    clear(n);
  }
  inline int find(int x) {
    assert(0 <= x && x < n);
    return (f[x] == x ? x : f[x] = find(f[x]));
  }
  inline int getSize(int x) {
    assert(0 <= x && x < n);
    return sz[find(x)];
  }
  inline int merge(int x, int y) {
    assert(0 <= x && x < n);
    assert(0 <= y && y < n);
    x = find(x);
    y = find(y);
    if (x == y) return false;
    if (depth[x] > depth[y]) {
      f[y] = x;
      sz[x] += sz[y];
    } else if (depth[y] > depth[x]) {
      f[x] = y;
      sz[y] += sz[x];
    } else {
      sz[y] += sz[x];
      f[x] = y;
      depth[y]++;
    }
    return true;
  }
  inline int same(int x, int y) {
    assert(0 <= x && x < n);
    assert(0 <= y && y < n);
    return (find(x) == find(y));
  }
  ~DSU() {
    delete[] f;
    delete[] depth;
    delete[] sz;
  }
};
struct PersistentDSU : public DSU {
  int find(int x) { return (x == f[x] ? x : find(f[x])); }
  inline int merge(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) return false;
    if (depth[x] > depth[y]) {
      f[y] = x;
      sz[x] += sz[y];
    } else if (depth[y] > depth[x]) {
      f[x] = y;
      sz[y] += sz[x];
    } else {
      sz[y] += sz[x];
      f[x] = y;
      depth[y]++;
    }
    return true;
  }
};
long long _Rand_Gen_Num() { return 1LL * rand() * RAND_MAX + rand(); }
int rand(int l, int r) {
  long long x = _Rand_Gen_Num();
  return x % (r - l + 1) + l;
}
template <typename Iterator>
void _m_random_shuffle(Iterator begin, Iterator end) {
  for (Iterator it = begin + 1; it != end; it++) {
    iter_swap(begin + rand(0, it - begin), it);
  }
}
using namespace std;
int n, k;
int d[55];
int w[55][55];
vector<int> edges[55];
DSUAE dsu;
vector<pair<int, pair<int, int>>> vSort;
int best = inf;
int ch[55][55];
int t[55];
int s[55];
int calc() {
  int res = 0;
  dsu.clear(n);
  vSort.clear();
  int cnt = n;
  memset(t, 0, sizeof(t));
  for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
      if (ch[i][j]) {
        if (dsu.same(i, j)) return inf;
        t[i]++;
        t[j]++;
        res += w[i][j];
        dsu.merge(i, j);
        cnt--;
      } else {
        vSort.push_back(make_pair(w[i][j], make_pair(i, j)));
      }
    }
  }
  sort(vSort.begin(), vSort.end());
  for (auto &o : vSort) {
    int w = o.first, x = o.second.first, y = o.second.second;
    if (!dsu.same(x, y) && t[x] != d[x] && t[y] != d[y]) {
      dsu.merge(x, y);
      res += w;
      cnt--;
      t[x]++;
      t[y]++;
    }
  }
  return (cnt == 1 ? res : inf);
}
int main() {
  cin >> n >> k;
  memset(d, 0x3f, sizeof(d));
  for (int i = 0; i < k; i++) {
    cin >> d[i];
  }
  for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
      scanf("%d", w[i] + j);
      vSort.push_back(make_pair(w[i][j], make_pair(i, j)));
    }
  }
  dsu.init(n);
  vector<pair<int, int>> tmp;
  for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
      if (i < k) tmp.emplace_back(i, j);
    }
  }
  int now = calc();
  best = now;
  for (double T = 1000; T >= 0.001; T *= 0.9993) {
    int x, y;
    while (true) {
      pair<int, int> o = tmp[rand(0, tmp.size() - 1)];
      x = o.first, y = o.second;
      if (!ch[x][y] && (s[x] == d[x] || s[y] == d[y]))
        continue;
      else
        break;
    }
    s[x] -= ch[x][y];
    s[y] -= ch[x][y];
    ch[x][y] ^= 1;
    s[x] += ch[x][y];
    s[y] += ch[x][y];
    int delta = calc() - now;
    if (exp(-(double)delta / T) >= (double)rand(0, 1000000000) / 1000000000) {
      now += delta;
      chmin(best, now);
    } else {
      s[x] -= ch[x][y];
      s[y] -= ch[x][y];
      ch[x][y] ^= 1;
      s[x] += ch[x][y];
      s[y] += ch[x][y];
    }
  }
  cout << best << endl;
  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>
const int mod = 1000000007;
const int gmod = 3;
const int inf = 1039074182;
const double eps = 1e-9;
const double pi = 3.141592653589793238462643383279;
const long long llinf = 2LL * inf * inf;
template <typename T1, typename T2>
inline void chmin(T1 &x, T2 b) {
  if (b < x) x = b;
}
template <typename T1, typename T2>
inline void chmax(T1 &x, T2 b) {
  if (b > x) x = b;
}
inline void chadd(int &x, int b) {
  x += b - mod;
  x += (x >> 31 & mod);
}
template <typename T1, typename T2>
inline void chadd(T1 &x, T2 b) {
  x += b;
  if (x >= mod) x -= mod;
}
template <typename T1, typename T2>
inline void chmul(T1 &x, T2 b) {
  x = 1LL * x * b % mod;
}
template <typename T1, typename T2>
inline void chmod(T1 &x, T2 b) {
  x %= b, x += b;
  if (x >= b) x -= b;
}
template <typename T>
inline T mabs(T x) {
  return (x < 0 ? -x : x);
}
using namespace std;
using namespace std;
template <typename T>
ostream &operator<<(ostream &cout, const vector<T> &vec) {
  cout << "{";
  for (int i = 0; i < (int)vec.size(); i++) {
    cout << vec[i];
    if (i != (int)vec.size() - 1) cout << ',';
  }
  cout << "}";
  return cout;
}
template <typename T1, typename T2>
ostream &operator<<(ostream &cout, pair<T1, T2> p) {
  cout << "(" << p.first << ',' << p.second << ")";
  return cout;
}
template <typename T, typename T2>
ostream &operator<<(ostream &cout, set<T, T2> s) {
  vector<T> t;
  for (auto x : s) t.push_back(x);
  cout << t;
  return cout;
}
template <typename T, typename T2>
ostream &operator<<(ostream &cout, multiset<T, T2> s) {
  vector<T> t;
  for (auto x : s) t.push_back(x);
  cout << t;
  return cout;
}
template <typename T>
ostream &operator<<(ostream &cout, queue<T> q) {
  vector<T> t;
  while (q.size()) {
    t.push_back(q.front());
    q.pop();
  }
  cout << t;
  return cout;
}
template <typename T1, typename T2, typename T3>
ostream &operator<<(ostream &cout, map<T1, T2, T3> m) {
  for (auto &x : m) {
    cout << "Key: " << x.first << ' ' << "Value: " << x.second << endl;
  }
  return cout;
}
template <typename T1, typename T2>
void operator+=(pair<T1, T2> &x, const pair<T1, T2> y) {
  x.first += y.first;
  x.second += y.second;
}
template <typename T1, typename T2>
pair<T1, T2> operator+(const pair<T1, T2> &x, const pair<T1, T2> &y) {
  return make_pair(x.first + y.first, x.second + y.second);
}
template <typename T1, typename T2>
pair<T1, T2> operator-(const pair<T1, T2> &x, const pair<T1, T2> &y) {
  return make_pair(x.first - y.first, x.second - y.second);
}
template <typename T1, typename T2>
pair<T1, T2> operator-(pair<T1, T2> x) {
  return make_pair(-x.first, -x.second);
}
template <typename T>
vector<vector<T>> operator~(vector<vector<T>> vec) {
  vector<vector<T>> v;
  int n = vec.size(), m = vec[0].size();
  v.resize(m);
  for (int i = 0; i < m; i++) {
    v[i].resize(n);
  }
  for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
      v[i][j] = vec[j][i];
    }
  }
  return v;
}
void print0x(int x) {
  std::vector<int> vec;
  while (x) {
    vec.push_back(x & 1);
    x >>= 1;
  }
  std::reverse(vec.begin(), vec.end());
  for (int i = 0; i < (int)vec.size(); i++) {
    std::cout << vec[i];
  }
  std::cout << ' ';
}
template <typename T>
void print0x(T x, int len) {
  std::vector<int> vec;
  while (x) {
    std::cout << (x & 1);
    x >>= 1;
    len--;
  }
  while (len--) cout << 0;
}
vector<string> vec_splitter(string s) {
  s += ',';
  vector<string> res;
  while (!s.empty()) {
    res.push_back(s.substr(0, s.find(',')));
    s = s.substr(s.find(',') + 1);
  }
  return res;
}
void debug_out(vector<string> __attribute__((unused)) args,
               __attribute__((unused)) int idx,
               __attribute__((unused)) int LINE_NUM) {
  cerr << endl;
}
template <typename Head, typename... Tail>
void debug_out(vector<string> args, int idx, int LINE_NUM, Head H, Tail... T) {
  if (idx > 0)
    cerr << ", ";
  else
    cerr << "Line(" << LINE_NUM << ") ";
  stringstream ss;
  ss << H;
  cerr << args[idx] << " = " << ss.str();
  debug_out(args, idx + 1, LINE_NUM, T...);
}
struct DSUAE {
  int *f;
  inline void clear(int n) {
    for (int i = 0; i < n; i++) {
      f[i] = i;
    }
  }
  inline void init(int n) {
    f = new int[n + 5];
    clear(n);
  }
  inline int find(int x) { return (f[x] == x ? x : f[x] = find(f[x])); }
  inline bool merge(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) return 0;
    if (x & 1)
      f[x] = y;
    else
      f[y] = x;
    return 1;
  }
  inline bool same(int x, int y) { return (find(x) == find(y)); }
};
struct DSU {
  int *f;
  int *depth;
  int *sz;
  int n;
  inline void clear(int n) {
    for (int i = 0; i < n; i++) {
      f[i] = i;
      depth[i] = 1;
      sz[i] = 1;
    }
  }
  inline void init(int _n) {
    n = _n;
    f = new int[n + 5];
    depth = new int[n + 5];
    sz = new int[n + 5];
    clear(n);
  }
  inline int find(int x) {
    assert(0 <= x && x < n);
    return (f[x] == x ? x : f[x] = find(f[x]));
  }
  inline int getSize(int x) {
    assert(0 <= x && x < n);
    return sz[find(x)];
  }
  inline int merge(int x, int y) {
    assert(0 <= x && x < n);
    assert(0 <= y && y < n);
    x = find(x);
    y = find(y);
    if (x == y) return false;
    if (depth[x] > depth[y]) {
      f[y] = x;
      sz[x] += sz[y];
    } else if (depth[y] > depth[x]) {
      f[x] = y;
      sz[y] += sz[x];
    } else {
      sz[y] += sz[x];
      f[x] = y;
      depth[y]++;
    }
    return true;
  }
  inline int same(int x, int y) {
    assert(0 <= x && x < n);
    assert(0 <= y && y < n);
    return (find(x) == find(y));
  }
  ~DSU() {
    delete[] f;
    delete[] depth;
    delete[] sz;
  }
};
struct PersistentDSU : public DSU {
  int find(int x) { return (x == f[x] ? x : find(f[x])); }
  inline int merge(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) return false;
    if (depth[x] > depth[y]) {
      f[y] = x;
      sz[x] += sz[y];
    } else if (depth[y] > depth[x]) {
      f[x] = y;
      sz[y] += sz[x];
    } else {
      sz[y] += sz[x];
      f[x] = y;
      depth[y]++;
    }
    return true;
  }
};
long long _Rand_Gen_Num() { return 1LL * rand() * RAND_MAX + rand(); }
int rand(int l, int r) {
  long long x = _Rand_Gen_Num();
  return x % (r - l + 1) + l;
}
template <typename Iterator>
void _m_random_shuffle(Iterator begin, Iterator end) {
  for (Iterator it = begin + 1; it != end; it++) {
    iter_swap(begin + rand(0, it - begin), it);
  }
}
using namespace std;
int n, k;
int d[55];
int w[55][55];
vector<int> edges[55];
DSUAE dsu;
vector<pair<int, pair<int, int>>> vSort;
int best = inf;
int ch[55][55];
int t[55];
int s[55];
int calc() {
  int res = 0;
  dsu.clear(n);
  vSort.clear();
  int cnt = n;
  memset(t, 0, sizeof(t));
  for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
      if (ch[i][j]) {
        if (dsu.same(i, j)) return inf;
        t[i]++;
        t[j]++;
        res += w[i][j];
        dsu.merge(i, j);
        cnt--;
      } else {
        vSort.push_back(make_pair(w[i][j], make_pair(i, j)));
      }
    }
  }
  sort(vSort.begin(), vSort.end());
  for (auto &o : vSort) {
    int w = o.first, x = o.second.first, y = o.second.second;
    if (!dsu.same(x, y) && t[x] != d[x] && t[y] != d[y]) {
      dsu.merge(x, y);
      res += w;
      cnt--;
      t[x]++;
      t[y]++;
    }
  }
  return (cnt == 1 ? res : inf);
}
int main() {
  cin >> n >> k;
  memset(d, 0x3f, sizeof(d));
  for (int i = 0; i < k; i++) {
    cin >> d[i];
  }
  for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
      scanf("%d", w[i] + j);
      vSort.push_back(make_pair(w[i][j], make_pair(i, j)));
    }
  }
  dsu.init(n);
  vector<pair<int, int>> tmp;
  for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
      if (i < k) tmp.emplace_back(i, j);
    }
  }
  int now = calc();
  best = now;
  for (double T = 1000; T >= 0.001; T *= 0.9993) {
    int x, y;
    while (true) {
      pair<int, int> o = tmp[rand(0, tmp.size() - 1)];
      x = o.first, y = o.second;
      if (!ch[x][y] && (s[x] == d[x] || s[y] == d[y]))
        continue;
      else
        break;
    }
    s[x] -= ch[x][y];
    s[y] -= ch[x][y];
    ch[x][y] ^= 1;
    s[x] += ch[x][y];
    s[y] += ch[x][y];
    int delta = calc() - now;
    if (exp(-(double)delta / T) >= (double)rand(0, 1000000000) / 1000000000) {
      now += delta;
      chmin(best, now);
    } else {
      s[x] -= ch[x][y];
      s[y] -= ch[x][y];
      ch[x][y] ^= 1;
      s[x] += ch[x][y];
      s[y] += ch[x][y];
    }
  }
  cout << best << endl;
  return 0;
}

```