为人民服务

#include<bits/stdc++.h>
using namespace std;
int n,a,b,c;
int m[10][10],f[10][10][10][10];
int main(){
	cin>>n;
	while(cin>>a&&cin>>b&&cin>>c){
		if(a+b+c==0) break;
		m[a][b]=c;
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			for(int x=1;x<=n;x++){
				for(int y=1;y<=n;y++){
					int tmp1=max(f[i-1][j][x-1][y],f[i-1][j][x][y-1]);
					int tmp2=max(f[i][j-1][x-1][y],f[i][j-1][x][y-1]);
					f[i][j][x][y]=max(tmp1,tmp2)+m[i][j]+m[x][y];
					if(i==x&&j==y){
						f[i][j][x][y]-=m[i][j];
					}
				}
			}
		}
	}
	cout<<f[n][n][n][n]<<endl;
	return 0;
}