#include<iostream>
using namespace std;
int a[10][10],ans=0;int n;
int dx[4]={0,1},dy[4]={1,0};
#define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
template <typename T>
inline void read(T& r) {
	r=0;bool w=0; char ch=getchar();
	while(ch<'0'||ch>'9') w=ch=='-'?1:0,ch=getchar();
	while(ch>='0'&&ch<='9') r=r*10+(ch^48), ch=getchar();
	r=w?-r:r;
}
inline bool ok(int x,int y){
    return x<=n&&y<=n;
}
void dfs(int x1,int y1,int x2,int y2,int sum){
//cout<<x1<<" "<<y1<<" "<<endl;
    
    if(x1==n&&y1==n){
        ans=max(ans,sum);
        return;
    }
    for(int i=0;i<2;i++){
        int xx1=x1+dx[i],yy1=y1+dy[i];
        for(int j=0;j<2;j++){
            int xx2=x2+dx[j],yy2=y2+dy[j];
            if(ok(xx1,yy1)&&ok(xx2,yy2))dfs(xx1,yy1,xx2,yy2,
            sum+a[xx1][yy1]+a[xx2][yy2]*!(xx1==xx2&&yy1==yy2));
        }
    }
    
    
}
int main(){
    
    read(n);
    while(1){
        register int t1 , t2 , t3;
        read(t1);
        read(t2);
        read(t3);
        if(t1 == 0 && t2 == 0 && t3 == 0){
            break;
        }
        a[t1][t2] = t3;
    }
    dfs(1,1,1,1,a[1][1]);
    printf("%d",ans);
    return 0;
}

80pts，有什么优化吗？ 如果不用下载测试点不要脸大法，搜索能过吗？