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
#include<iostream>
#include<cstdio>
#include<string>
#include<cmath>
#include<vector>
#include<map>
#include<set>
#include<algorithm>
#include<utility>
using namespace std;

#define FOR(I,A,B) for(int I=(A);I<=(B);I++)
#define REP(I,N) for(int I=0;I<(N);I++)
#define ALL(X) (X).begin(),(X).end()
#define PB push_back
#define MP make_pair
#define f first
#define s second

typedef vector<int> VI;
typedef pair<int,int> PII;
typedef long long ll;
typedef vector<string> VS;

const int MAX = 2005;

int wsk[MAX];
vector < pair<int,pair<int,int> > > T;
vector < PII > base;
bool pos[MAX][MAX];

void update(PII &i, int idx){
	pos[i.f][i.s] = true;
	i.f = min(i.s,base[idx].s) + 1;
	i.s = max(i.s,base[idx].s);
}

int main(){
	int n,a;

	scanf("%d",&n);

	REP(i,n)
		REP(j,n-i){
			scanf("%d",&a);
			T.PB(MP(a,MP(i,i+j)));
		}

	sort(ALL(T));

	REP(i,n) wsk[i] = -1;

	ll res = 0;

	for(int j=0; j<T.size(); ++j){
		auto i = T[j].s;

		bool ok = true;
		while(wsk[i.f] != -1){
			if(pos[i.f][i.s]) break;
			update(i,wsk[i.f]);
			if(i.f>i.s){
				ok = false;
				break;
			}
		}

		if(ok&&wsk[i.f] == -1){
			res += T[j].f;
			wsk[i.f] = base.size();
			pos[i.f][i.s] = true;
			base.PB(i);
		}

		if(base.size() == n) break;
	}

	printf("%lld\n",res);

	return 0;
}