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
107
108
109
110
111
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
#define FOR(i,a,b) for(int i=(a); i<(b); ++i)
#define REP(i,n) FOR(i,1,(n)+1)
typedef vector<int> vi;
#define pb push_back
typedef pair<int,int> pii;
#define mp make_pair
#define st first
#define nd second
typedef long long ll;
#define INF 1000000001
#define sz size()
#define VAR(n,v) typeof(v) n=(v)
#define ALL(t) t.begin(),t.end()
#define SC(a) scanf("%d", &a)
#define GET(a) int a; SC(a)
#define ISDEBUG 0
#define dprintf(...) if(ISDEBUG) \
{printf("\033[31m"); printf(__VA_ARGS__); printf("\033[0m");}
template <class It> void dptab(It b, It e, const char* f="%d ") {
	if(ISDEBUG) {
		for(It it=b; it!=e; ++it) dprintf(f, *it); dprintf("\n");
}}

struct test {
	int u, v;
	int cost;
	test(int u, int v, int cost): u(u), v(v), cost(cost) {}
	bool operator<(const test &t) const {
		if(cost!=t.cost)
			return cost < t.cost;
		else if(u!=t.u)
			return u < t.u;
		else if(v!=t.v)
			return v < t.v;
	}
};

int n;

vi get_vector(test &t) {
	vi v;
	FOR(i,0,n) {
		if(i>=t.u && i<t.v) v.pb(1);
		else v.pb(0);
	}
	return v;
}

bool linear_independent(vector<vi> &m, vi &v) {
	dptab(ALL(v));
	FOR(i,0,n) {
		if(v[i]) {
			FOR(row,0,m.sz) {
				int first = true;
				FOR(j,0,i) if(m[row][j]) first=false;
				if(m[row][i] && first) {
					int d = v[i]/m[row][i];
					FOR(col,0,n) {
						v[col] -= d*m[row][col];
					}
				}
			}
		}
	}
	FOR(i,0,v.sz)
		if(v[i]) return true;
	return false;
} 



int main() {
	SC(n);
	vector<test> tests;
	FOR(i,0,n)
		FOR(j,i,n) {
			GET(cost);
			tests.pb(test(i,j+1,cost));
		}
	vector<test> solution;
	vector<vi> matrix;

	sort(ALL(tests));
	FOR(i,0,tests.sz) {
		vi v = get_vector(tests[i]);
		if(linear_independent(matrix, v)) {
			solution.pb(tests[i]);
			matrix.pb(v);
		}
		
		if(solution.sz == n)
			break;
	}
	ll sum = 0;
	FOR(i,0,solution.sz) {
		dprintf("%d %d\n", solution[i].u, solution[i].v);
		sum += solution[i].cost;
	}
	printf("%lld\n", sum);
	return 0;
}