#include<cstdio> #include<iostream> using namespace std; const int N=11; int dp1[N][N],dp2[N][N],n,o; struct point { int x; int y; int num; }poi[N*N]; void find(int k,int l)//判断第一遍走过哪些点 { if(k==0&&l==0) { return; } else { if(dp1[k][l]-dp2[k][l]==dp1[k-1][l]) { dp2[k][l]=0; find(k-1,l); } else if(dp1[k][l]-dp2[k][l]==dp1[k][l-1]) { dp2[k][l]=0; find(k,l-1); } } } int main() { scanf("%d",&n); for(;;) { o++; scanf("%d%d%d",&poi[o].x,&poi[o].y,&poi[o].num); if(poi[o].x==poi[o].y&&poi[o].y==poi[o].num&&poi[o].num==0) { break; } else { dp1[poi[o].x][poi[o].y]=poi[o].num; dp2[poi[o].x][poi[o].y]=poi[o].num; } } for(int i=1;i<=n;i++)//第一遍的最优解 { for(int j=1;j<=n;j++) { dp1[i][j]+=max(dp1[i-1][j],dp1[i][j-1]); } } find(n,n); for(int i=1;i<=n;i++)//第二遍的最优解 { for(int j=1;j<=n;j++) { dp2[i][j]+=max(dp2[i-1][j],dp2[i][j-1]); } } printf("%d",dp1[n][n]+dp2[n][n]);//输出答案 return 0; }