#include <bits/stdc++.h>
using namespace std;
[[maybe_unused]] constexpr int INF = (numeric_limits<int>::max()) / 2;
[[maybe_unused]] constexpr long long INFLL =
    (numeric_limits<long long>::max()) / 2;
[[maybe_unused]] constexpr __int128 INF128 = numeric_limits<__int128>::max();
template <class T>
istream &operator>>(istream &is, vector<T> &a) {
  for (auto &i : a) is >> i;
  return is;
}
#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target( \
    "sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("fast-math")
#pragma GCC optimize("section-anchors")
#pragma GCC optimize("profile-values,profile-reorder-functions,tracer")
#pragma GCC optimize("vpt")
#pragma GCC optimize("rename-registers")
#pragma GCC optimize("move-loop-invariants")
#pragma GCC optimize("unswitch-loops")
#pragma GCC optimize("function-sections")
#pragma GCC optimize("data-sections")
#pragma GCC optimize("branch-target-load-optimize")
#pragma GCC optimize("branch-target-load-optimize2")
#pragma GCC optimize("btr-bb-exclusive")
mt19937 gen(chrono::high_resolution_clock::now().time_since_epoch().count());
int getrand(int l, int r) { return uniform_int_distribution<int>(l, r)(gen); }
long double getrand(long double l, long double r) {
  return uniform_real_distribution<long double>(l, r)(gen);
}
vector<vector<int>> w;
vector<int> gg;
long long check(vector<pair<int, int>> t) {
  long long ans = 0;
  for (auto [i, j] : t) ans += w[i][j];
  return ans;
}
struct dsu {
  vector<int> p, s;
  dsu(){};
  dsu(int n) {
    p.resize(n);
    s.resize(n, 1);
    iota(p.begin(), p.end(), 0);
  }
  int get(int v) {
    if (p[v] == v) return v;
    return p[v] = get(p[v]);
  }
  void unite(int a, int b) {
    a = get(a);
    b = get(b);
    if (a == b) return;
    if (s[a] < s[b]) swap(a, b);
    s[a] += s[b];
    p[b] = a;
  }
};
int n;
void get(vector<pair<int, int>> &t, vector<int> &d) {
  int i = getrand(0, n - 2);
  int govno = 1;
  while (govno++ < 228) {
    if (govno % 20 == 0) i = getrand(0, n - 2);
    auto dd = d;
    dsu tmp(n);
    for (int j = 0; j < n - 1; ++j) {
      if (j != i) tmp.unite(t[j].first, t[j].second);
    }
    int v = getrand(0, n - 1), u = getrand(0, n - 1);
    while (tmp.get(u) == tmp.get(v)) u = getrand(0, n - 1);
    --dd[t[i].first];
    --dd[t[i].second];
    ++dd[v];
    ++dd[u];
    bool check = true;
    for (int ggi = 0; ggi < gg.size(); ++ggi) {
      if (dd[ggi] > gg[ggi]) check = false;
    }
    if (check) {
      t.erase(t.begin() + i);
      t.push_back({u, v});
      d = dd;
      return;
    }
  }
}
int main() {
  cin.tie(0)->sync_with_stdio(0);
  int k;
  cin >> n >> k;
  gg.resize(k);
  cin >> gg;
  w.resize(n, vector<int>(n, INF));
  for (int i = 0; i < n; ++i) {
    for (int j = i + 1; j < n; ++j) {
      cin >> w[i][j];
      w[j][i] = w[i][j];
    }
  }
  if (n < 8) {
    long long ans = INF;
    int m = n * (n - 1) / 2;
    vector<pair<int, int>> govno;
    for (int i = 0; i < n; ++i)
      for (int j = i + 1; j < n; ++j) govno.push_back({i, j});
    for (int mask = 0; mask < (1 << m); ++mask) {
      if (__builtin_popcount(mask) != n - 1) continue;
      dsu tmp(n);
      long long cur = 0;
      vector<int> d(n, 0);
      for (int i = 0; i < m; ++i)
        if ((mask >> i) & 1) {
          tmp.unite(govno[i].first, govno[i].second);
          ++d[govno[i].first];
          ++d[govno[i].second];
          cur += w[govno[i].first][govno[i].second];
        }
      bool check = true;
      for (int i = 0; i < n; ++i)
        if (tmp.get(0) != tmp.get(i)) check = false;
      for (int i = 0; i < k; ++i)
        if (d[i] > gg[i]) check = false;
      if (check) ans = min(ans, cur);
    }
    cout << ans;
    return 0;
  }
  int timera = 0;
  long long ans = INF;
  while (timera++ < 200) {
    long double temp = 1;
    int timerb = 0;
    vector<pair<int, int>> t;
    vector<int> d(n, 0);
    if (count(gg.begin(), gg.end(), 1) > 2) {
      dsu tmp(n);
      vector<int> zhopa(n);
      iota(zhopa.begin(), zhopa.end(), 0);
      int root = getrand(k, n - 1);
      for (int i = 0; i < k; ++i) {
        if (gg[i] == 1) {
          tmp.unite(i, root);
          zhopa.erase(find(zhopa.begin(), zhopa.end(), i));
          ++d[root];
          ++d[i];
          t.push_back({i, root});
        }
      }
      while (t.size() < n - 1) {
        int u = zhopa[getrand(0, zhopa.size() - 1)],
            v = zhopa[getrand(0, zhopa.size() - 1)];
        while (1) {
          while (tmp.get(u) == tmp.get(v)) v = getrand(0, n - 1);
          if (u < k && d[u] + 1 > gg[u] || v < k && d[v] + 1 > gg[v]) {
            u = getrand(0, n - 1);
            continue;
          }
          ++d[u];
          if (u < k && d[u] == gg[u])
            zhopa.erase(find(zhopa.begin(), zhopa.end(), u));
          ++d[v];
          if (v < k && d[v] == gg[v])
            zhopa.erase(find(zhopa.begin(), zhopa.end(), v));
          tmp.unite(u, v);
          t.push_back({u, v});
          break;
        }
      }
    } else {
      int leaf1 = 0, leaf2 = n - 1;
      if (count(gg.begin(), gg.end(), 1) >= 1)
        leaf1 = find(gg.begin(), gg.end(), 1) - gg.begin();
      if (count(gg.begin(), gg.end(), 1) == 2) {
        for (int i = k - 1; i >= 0; --i)
          if (gg[i] == 1) {
            leaf2 = i;
            break;
          }
      }
      for (int i = 0; i + 1 < n; ++i) t.push_back({i, i + 1});
      int govno1 = 0, govno2 = n - 1;
      for (int i = 0; i + 1 < n; ++i) {
        if (t[i].first == govno1) t[i].first = leaf1;
        if (t[i].second == govno2) t[i].second = leaf2;
        if (t[i].first == leaf1) t[i].first = govno1;
        if (t[i].second == leaf2) t[i].second = govno2;
      }
      for (auto [i, j] : t) {
        ++d[i];
        ++d[j];
      }
    }
    ans = min(ans, check(t));
    while (timerb++ < 10000) {
      temp *= 0.99;
      auto oldt = t;
      auto oldd = d;
      get(t, d);
      long long res = check(oldt) - check(t);
      if (exp((long double)res / temp) >
          getrand((long double)0.0, (long double)1.0)) {
        ans = min(ans, check(t));
        continue;
      }
      t = oldt;
      d = oldd;
    }
  }
  cout << ans;
  cout << "\n";
}

### 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>
using namespace std;
[[maybe_unused]] constexpr int INF = (numeric_limits<int>::max()) / 2;
[[maybe_unused]] constexpr long long INFLL =
    (numeric_limits<long long>::max()) / 2;
[[maybe_unused]] constexpr __int128 INF128 = numeric_limits<__int128>::max();
template <class T>
istream &operator>>(istream &is, vector<T> &a) {
  for (auto &i : a) is >> i;
  return is;
}
#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target( \
    "sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("fast-math")
#pragma GCC optimize("section-anchors")
#pragma GCC optimize("profile-values,profile-reorder-functions,tracer")
#pragma GCC optimize("vpt")
#pragma GCC optimize("rename-registers")
#pragma GCC optimize("move-loop-invariants")
#pragma GCC optimize("unswitch-loops")
#pragma GCC optimize("function-sections")
#pragma GCC optimize("data-sections")
#pragma GCC optimize("branch-target-load-optimize")
#pragma GCC optimize("branch-target-load-optimize2")
#pragma GCC optimize("btr-bb-exclusive")
mt19937 gen(chrono::high_resolution_clock::now().time_since_epoch().count());
int getrand(int l, int r) { return uniform_int_distribution<int>(l, r)(gen); }
long double getrand(long double l, long double r) {
  return uniform_real_distribution<long double>(l, r)(gen);
}
vector<vector<int>> w;
vector<int> gg;
long long check(vector<pair<int, int>> t) {
  long long ans = 0;
  for (auto [i, j] : t) ans += w[i][j];
  return ans;
}
struct dsu {
  vector<int> p, s;
  dsu(){};
  dsu(int n) {
    p.resize(n);
    s.resize(n, 1);
    iota(p.begin(), p.end(), 0);
  }
  int get(int v) {
    if (p[v] == v) return v;
    return p[v] = get(p[v]);
  }
  void unite(int a, int b) {
    a = get(a);
    b = get(b);
    if (a == b) return;
    if (s[a] < s[b]) swap(a, b);
    s[a] += s[b];
    p[b] = a;
  }
};
int n;
void get(vector<pair<int, int>> &t, vector<int> &d) {
  int i = getrand(0, n - 2);
  int govno = 1;
  while (govno++ < 228) {
    if (govno % 20 == 0) i = getrand(0, n - 2);
    auto dd = d;
    dsu tmp(n);
    for (int j = 0; j < n - 1; ++j) {
      if (j != i) tmp.unite(t[j].first, t[j].second);
    }
    int v = getrand(0, n - 1), u = getrand(0, n - 1);
    while (tmp.get(u) == tmp.get(v)) u = getrand(0, n - 1);
    --dd[t[i].first];
    --dd[t[i].second];
    ++dd[v];
    ++dd[u];
    bool check = true;
    for (int ggi = 0; ggi < gg.size(); ++ggi) {
      if (dd[ggi] > gg[ggi]) check = false;
    }
    if (check) {
      t.erase(t.begin() + i);
      t.push_back({u, v});
      d = dd;
      return;
    }
  }
}
int main() {
  cin.tie(0)->sync_with_stdio(0);
  int k;
  cin >> n >> k;
  gg.resize(k);
  cin >> gg;
  w.resize(n, vector<int>(n, INF));
  for (int i = 0; i < n; ++i) {
    for (int j = i + 1; j < n; ++j) {
      cin >> w[i][j];
      w[j][i] = w[i][j];
    }
  }
  if (n < 8) {
    long long ans = INF;
    int m = n * (n - 1) / 2;
    vector<pair<int, int>> govno;
    for (int i = 0; i < n; ++i)
      for (int j = i + 1; j < n; ++j) govno.push_back({i, j});
    for (int mask = 0; mask < (1 << m); ++mask) {
      if (__builtin_popcount(mask) != n - 1) continue;
      dsu tmp(n);
      long long cur = 0;
      vector<int> d(n, 0);
      for (int i = 0; i < m; ++i)
        if ((mask >> i) & 1) {
          tmp.unite(govno[i].first, govno[i].second);
          ++d[govno[i].first];
          ++d[govno[i].second];
          cur += w[govno[i].first][govno[i].second];
        }
      bool check = true;
      for (int i = 0; i < n; ++i)
        if (tmp.get(0) != tmp.get(i)) check = false;
      for (int i = 0; i < k; ++i)
        if (d[i] > gg[i]) check = false;
      if (check) ans = min(ans, cur);
    }
    cout << ans;
    return 0;
  }
  int timera = 0;
  long long ans = INF;
  while (timera++ < 200) {
    long double temp = 1;
    int timerb = 0;
    vector<pair<int, int>> t;
    vector<int> d(n, 0);
    if (count(gg.begin(), gg.end(), 1) > 2) {
      dsu tmp(n);
      vector<int> zhopa(n);
      iota(zhopa.begin(), zhopa.end(), 0);
      int root = getrand(k, n - 1);
      for (int i = 0; i < k; ++i) {
        if (gg[i] == 1) {
          tmp.unite(i, root);
          zhopa.erase(find(zhopa.begin(), zhopa.end(), i));
          ++d[root];
          ++d[i];
          t.push_back({i, root});
        }
      }
      while (t.size() < n - 1) {
        int u = zhopa[getrand(0, zhopa.size() - 1)],
            v = zhopa[getrand(0, zhopa.size() - 1)];
        while (1) {
          while (tmp.get(u) == tmp.get(v)) v = getrand(0, n - 1);
          if (u < k && d[u] + 1 > gg[u] || v < k && d[v] + 1 > gg[v]) {
            u = getrand(0, n - 1);
            continue;
          }
          ++d[u];
          if (u < k && d[u] == gg[u])
            zhopa.erase(find(zhopa.begin(), zhopa.end(), u));
          ++d[v];
          if (v < k && d[v] == gg[v])
            zhopa.erase(find(zhopa.begin(), zhopa.end(), v));
          tmp.unite(u, v);
          t.push_back({u, v});
          break;
        }
      }
    } else {
      int leaf1 = 0, leaf2 = n - 1;
      if (count(gg.begin(), gg.end(), 1) >= 1)
        leaf1 = find(gg.begin(), gg.end(), 1) - gg.begin();
      if (count(gg.begin(), gg.end(), 1) == 2) {
        for (int i = k - 1; i >= 0; --i)
          if (gg[i] == 1) {
            leaf2 = i;
            break;
          }
      }
      for (int i = 0; i + 1 < n; ++i) t.push_back({i, i + 1});
      int govno1 = 0, govno2 = n - 1;
      for (int i = 0; i + 1 < n; ++i) {
        if (t[i].first == govno1) t[i].first = leaf1;
        if (t[i].second == govno2) t[i].second = leaf2;
        if (t[i].first == leaf1) t[i].first = govno1;
        if (t[i].second == leaf2) t[i].second = govno2;
      }
      for (auto [i, j] : t) {
        ++d[i];
        ++d[j];
      }
    }
    ans = min(ans, check(t));
    while (timerb++ < 10000) {
      temp *= 0.99;
      auto oldt = t;
      auto oldd = d;
      get(t, d);
      long long res = check(oldt) - check(t);
      if (exp((long double)res / temp) >
          getrand((long double)0.0, (long double)1.0)) {
        ans = min(ans, check(t));
        continue;
      }
      t = oldt;
      d = oldd;
    }
  }
  cout << ans;
  cout << "\n";
}

```