1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <iostream>
#include <limits>
#include <vector>

using namespace std;

#define maxi numeric_limits<int>::max()

vector< vector<int> > c;
int n;
int rem;

vector<int> minc;

inline int cost(int i, int j) {
  if (i < j)
    return c[i][j-1 -i];
  else
    return c[j][i-1 -j];
}

long long go() {
  long long ret = 0;
  minc.resize(n);
  rem = n;
  for (int i = 0; i < n; i++) {
    minc[i] = cost(n, i);
  }
  while (rem > 0) {
    int _minv = maxi;
    int _mini = -1;
    for (int i = 0; i < n; i++) {
      if (minc[i] < _minv) {
        _mini = i;
        _minv = minc[i];
      }
    }
    minc[_mini] = maxi;
    ret += _minv;
    rem--;
    for (int i = 0; i < n; i++) {
      if (minc[i] != maxi) {
        int cij = cost(_mini, i);
        if (cij < minc[i])
          minc[i] = cij;
      }
    }
  }
  return ret;
}


int main() {
  ios::sync_with_stdio(false);
  cin >> n;
  c.resize(n);
  for (int i = 0; i < n; i++) {
    c[i].resize(n-i);
    for (int j = 0; j < n-i; j++)
      cin >> c[i][j];
  }
  cout << go() << endl;
  return 0;
}