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
program kuglarz;

type przedzial=record
	pocz,kon : integer;
	cena : longint;
end;

type tab = array [1..2048,1..2048] of boolean; 
type tab2 = array [1..3000000] of przedzial;
type tab3 = array [1..2048] of integer; 

var k,pom,n,m : longint;
	i,j : integer;
	wiedza : tab;
	lista : tab2;
	suma : int64;

	procedure quick(od,do_ : longint);
	var i,j,x : longint;
		temp : przedzial;
	begin
		i:=od;
		j:=do_;
		x:=lista[(od+do_) div 2].cena;
		repeat
			while lista[i].cena<x do inc(i);
			while x<lista[j].cena do dec(j);
			if i<=j then begin
				temp:=lista[i];
				lista[i]:=lista[j];
				lista[j]:=temp;
				inc(i);
				dec(j);
			end;
		until i>j;
		if od<j then quick(od,j);
		if i<do_ then quick(i,do_);
	end;
	
	function sensowne(odcinek : przedzial):boolean;
	begin
		sensowne:=not wiedza[odcinek.pocz,odcinek.kon];
	end;
	
	procedure poglebWiedze(odcinek : przedzial);
	var pom1,pom2,i,k : integer;
		male : tab3;
	begin
		pom1:=odcinek.pocz-1;
		pom2:=odcinek.kon+1;
		k:=1;
		wiedza[odcinek.pocz,odcinek.kon]:=true;
		if pom1>0 then begin
			for i:=1 to pom1 do
				if wiedza[i,pom1]=true then begin
					wiedza[i,odcinek.kon]:=true;
					male[k]:=i;
					inc(k);	
				end;
		end;
		if pom2<=n then begin
			for i:=pom2 to n do
				if wiedza[pom2,i]=true then begin
					wiedza[odcinek.pocz,i]:=true;
					for j:=1 to k-1 do 
						wiedza[male[j],i]:=true;
				end;
		end;
		for i:=odcinek.pocz+1 to odcinek.kon-1 do begin
			if wiedza[odcinek.pocz,i] then
				wiedza[i+1,odcinek.kon]:=true;
			if wiedza[i,odcinek.kon] then
				wiedza[odcinek.pocz,i-1]:=true;
		end;
	end;
	
begin
	k:=1;
	suma:=0;
	readln(n);
	m:=n*(n+1) div 2;
	for i:=1 to n do begin
		for j:=i to n do begin
			read(pom);
			wiedza[i,j]:=false;
			lista[k].cena:=pom;
			lista[k].pocz:=i;
			lista[k].kon:=j;
			inc(k);
		end;
		readln;
	end;
	quick(1,m);
	i:=0;
	k:=1;
	while (i<n)and(k<=m) do begin
		if (sensowne(lista[k])) then begin
			poglebWiedze(lista[k]);
			inc(suma,lista[k].cena);
			inc(i);
		end;
		inc(k);
	end;
	writeln(suma);
end.