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
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
#include<algorithm>
#include<bitset>
#include<cassert>
#include<complex>
#include<cstdio>
#include<cstring>
#include<iomanip>
#include<iostream>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<vector>
#define FOR(i, a, b) for(int i =(a); i <=(b); ++i)
#define FORD(i, a, b) for(int i = (a); i >= (b); --i)
#define REP(i, n) for(int i = 0;i <(n); ++i)
#define VAR(v, i) __typeof(i) v=(i)
#define FORE(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i)
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
#define PB push_back
#define MP make_pair
#define X first
#define Y second 
#define debug(x) {cerr <<#x <<" = " <<x <<endl; }
#define debugv(x) {{cerr <<#x <<" = "; FORE(itt, (x)) cerr <<*itt <<", "; cerr <<endl; }}
using namespace std;
typedef long long LL;
typedef long double LD;
typedef pair<int, int> PII;
typedef vector<int> VI;

template<class C> void mini(C&a4, C b4){a4=min(a4, b4); }
template<class C> void maxi(C&a4, C b4){a4=max(a4, b4); }
template<class T1, class T2>
ostream& operator<< (ostream &out, pair<T1, T2> pair) { return out << "(" << pair.X << ", " << pair.Y << ")";}

#define N 2000
LL c[N][N];
bool have[N][N];
int yy[N];
int xx[N];

bool add(int x, int y) {
	while(true) {
		if(have[x][y]) {
			return false;
		};
		have[x][y] = true;
		int nx, ny;
		if(yy[x] != -1) {
			if(yy[x] > y) {
				nx = y+1;
				ny = yy[x];

				yy[x] = y;
				xx[ny] = -1;
			} else {
				nx = yy[x]+1;
				ny = y;
			}
		} else if(xx[y] != -1) {
			if(x < xx[y]) {
				ny = x-1;
				nx = x;
			} else {
				nx = xx[y];
				ny = x-1;

				xx[y] = x;
				yy[nx] = -1;
			};
		} else {
			xx[y] = x;
			yy[x] = y;
			return true;
		};

		x=nx;
		y=ny;
	};
};

vector<pair<int, pair<int,int> >  >  allp;

int main(){
	int n;
	scanf("%d", &n);
	REP(i, n) yy[i] = xx[i] = -1;
	REP(i, n) FOR(j, i, n-1) {
		scanf("%lld", &c[i][j]);
		allp.PB(MP(c[i][j], MP(i,j)));
		
	};

	sort(ALL(allp));

	LL cost = 0;

	for(auto &q : allp) {
		if(add(q.Y.X, q.Y.Y)) cost += q.X;
	};
	printf("%lld\n", cost);
    return 0;
}