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

using namespace std;

class vpair{
	public:
		int start;
		int end;
		int value;
		vpair(int s, int e, int v){
			start = s;
			end = e;
			value = v;
		}
		void show(){
			printf("start = %d, end = %d, value = %d\n", start, end ,value);
		}
	
};
class matrix{
	public:
		matrix(int s){
			size = 0;
			maxSize  = s;
			value = 0;
		}
		int size;
		int maxSize;
		int value;
		vector<vector<bool> > cont;
		vector<int> index;
		void add(vpair p){
			int i, j;
			cont.push_back(*(new vector<bool>()));
			for(i = 0; i < maxSize; i++){
				cont[size].push_back(i + 1 >= p.start && i + 1 <= p.end);
			}
			for(i = 0; i < size; i++){
				j = index[i];
				if(cont[size][j])
					for(j = 0; j < maxSize; j++)
						cont[size][j] = (cont[size][j] != cont[i][j]);
			}
			j = - 1;
			for(i = 0; i < maxSize; i++) if(cont[size][i]) j = i;
			if( j == - 1){ cont.erase(cont.end()); //printf("nie dodalem\n");
			}
			else {index.push_back(j); //printf("dodalem\n");
				size++;
				value += p.value;}
//		wypisz();
		};
				
		bool full(){return size == maxSize;}
		void wypisz(){
			for(int i = 0; i < size; i++){
				for(int j = 0; j < maxSize; j++){
					if(cont[i][j]) printf("1 ");
					else printf("0 ");
				}
				printf("\n");
			}
		};
		
};

class vpairCompare{
	public:
		bool operator()(const vpair& a, const vpair& b){
			return a.value > b.value;
		}
};

int main(){

	priority_queue<vpair, vector<vpair>, vpairCompare> cand;
	int n,v;
	vpair *x;
	scanf("%d", &n);
	matrix *base = new matrix(n);
	for(int i = 1; i <= n; i++){
		for(int j = i; j <= n; j++){
			scanf("%d", &v);
			x = new vpair(i,j,v);
			cand.push(*x);
		}
	}
//	while(!cand.empty()){
	while(!base->full()){
		*x = cand.top();
		cand.pop();
//		x->show();
		base->add(*x);
	}
	printf("%d\n", base->value);
return 0;

}