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
#include<algorithm>
//#include<stdio.h>
#include<iostream>
#include<list>
#include<map>
#include<queue>
#define FOR(i,n) for(int i = 0;i<n;++i)
#define FORI(i,b,n) for(int i = b;i<n;++i)
#define FORD(i,n) for(int i = n;i>=0;--i)
#define ZERO 0.000001
#define MAX ((1<<31)-1)
#define qprintf debug && printf
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define ull long long int
using namespace std;
#define POINTER_TO(i,j) (&(t[(i)][(j)-(i)-1]))
class Range
{
	public:
	int from;
	int to;
	int price;
	int alive;
	list<Range*> back;
};
struct RC {
	bool operator() (const Range* a, const Range* b){return a->price < b->price;}
};
void markAndFollow(Range*r){
	if(r->alive==2)return;
	r->alive=2;
	while(!r->back.empty()){
		Range*f=r->back.front();
		r->back.pop_front();
		markAndFollow(f);
	}
}
int main(){
	ios_base::sync_with_stdio(0);
	int n;
	cin>>n;//scanf("%d",&n);
	Range**t=new Range*[n];
	int nn=(n*(n+1))/2;
	*t=new Range[nn];
	FOR(i,n){
		t[i]=*t+i*(n+n+1-i)/2;
	}
	Range**q=new Range*[nn];
	int y=0;
	FOR(i,n){
		FORI(j,i,n){
			int p;
			cin>>p;//scanf("%d",&p);
			int ji=j-i;
			t[i][ji].alive=1;
			t[i][ji].price=p;
			t[i][ji].from=i;
			t[i][ji].to=j+1;
			q[y]=&(t[i][ji]);
			++y;
		}
	}
	RC cmp;
	sort(q,q+nn,cmp);
	ull p=0;
	FOR(u,nn){
		Range*r=q[u];
		if(r->alive!=1)continue;
		p+=r->price;
		markAndFollow(r);
		FOR(i,n+1){
			if(i==r->from || i==r->to)continue;

			Range*cheaper;
			Range*third;
			if(i<r->from){
				cheaper=POINTER_TO(i,r->from);
				third=POINTER_TO(i,r->to);
			}else
			if(r->from<i && i<r->to){
				cheaper=POINTER_TO(r->from,i);
				third=POINTER_TO(i,r->to);
			}else
			if(i>r->to){
				cheaper=POINTER_TO(r->from,i);
				third=POINTER_TO(r->to,i);
			}


			if(cheaper->alive==2 || third->alive==2){
				markAndFollow(cheaper);
				markAndFollow(third);
				continue;
			}
			if(cheaper->price>third->price){
				if(third->alive==1)
					swap(cheaper,third);
			}
			third->alive=0;
			third->back.push_back(cheaper);
			cheaper->back.push_back(third);
		}
	}
	cout<<p<<endl;;//printf("%llu\n",p);
	return 0;
}