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 <cstdio>
#include <algorithm>
#include <vector>

#define ST first
#define ND second

using namespace std;

const int MX = 2e3+10;

typedef long long int LL;

int n, nx[MX*2], p[MX*2];
vector<pair<int, pair<int, int> > > Q;
LL W;

void make_set() {
	for (int i = 1; i <= 2*n; i++) p[i] = i;
}

int find(int a) {
	if (p[a] == a) return a;
	return p[a] = find(p[a]);
}

int uni(int a, int b) {
	p[find(a)] = p[find(b)];
}

void print_all() {
	for (int i = 1; i <= n; i++) printf("%d: %d %d (%d %d)\n", i, nx[i], nx[i+n], find(i), find(n+i));
	printf("\n");
}

void ins(int where, int len) {
	if (where <= 0 || where > n) return;
	//printf("attempting to insert %d %d (%d)\n", where, len, nx[where]);
	
	if (len == 0) return;
	if (find(where) == find(n+where+len-1) && (nx[where] != 0 && len >= nx[where])) return;
	
	if (where > 1) uni(n+where-1, n+where+len-1);
	uni(where, n+where+len-1);
	if (where+len <= n) uni(where, where+len);
	
	//printf("inserting %d, %d\n", where, len);
	
	int A = nx[where];
	int B = len;
	if (A > B) swap(A, B);
	
	nx[where] = (A == 0 ? B : A);
	
	ins(where, A);
	
	int C = nx[n+where+A-1];
	int D = A;
	if (C > D) swap(C, D);
	nx[n+where+A-1] = (C == 0 ? D : C);
	ins(where+A-1-C+1, C);
	ins(where+A-1-D+1, D-C);
	
	ins(where+A, B-A);
	
	C = nx[n+where+B-1];
	D = B;
	if (C > D) swap(C, D);
	nx[n+where+B-1] = (C == 0 ? D : C);
	ins(where+B-1-C+1, C);
	ins(where+B-1-D+1, D-C);
	
	
}

int l;

void check(int cost, int beg, int end) {
	if (find(beg) == find(n+end)) return;
	//printf("checking %d %d %d\n", cost, beg, end);
	ins(beg, end-beg+1);
	//print_all();
	W = W + cost;
	l++;
}

int main() {
	scanf("%d", &n);
	make_set();
	for (int i = 1; i <= n; i++) for (int j = i; j <= n; j++) {
		int c; scanf("%d", &c);
		Q.push_back(make_pair(c, make_pair(i, j)));
	}
	sort(Q.begin(), Q.end());
	
	for (int i = 0; i < Q.size(); i++) {
		if (l == n) break;
		check(Q[i].ST, Q[i].ND.ST, Q[i].ND.ND);
	}
	
	//printf("%d %d\n", l, n);
	
	printf("%lld\n", W);
	
	return 0;
}