```cpp
#include<bits/stdc++.h>
using namespace std;
int m[105][105];
int dp[55][55][55][55];
int main()
{
int n,i,j,k,l;
scanf("%d",&n);
while(1)
{
int x,y,c;
scanf("%d%d%d",&x,&y,&c);
if(!x&&!y&&!c) break;
m[x][y]=c;
}
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
for(k=1;k<=n;k++)
for(l=1;l<=n;l++)
{
int s1=max(dp[i-1][j][k-1][l],dp[i-1][j][k][l-1]);
int s2=max(dp[i][j-1][k-1][l],dp[i][j-1][k][l-1]);
int pls=m[i][j]+m[k][l];
if(i==k&&j==l)
pls-=m[i][j];
dp[i][j][k][l]=max(s1,s2)+pls;
}
printf("%d",dp[n][n][n][n]);
return 0;
}
```
by 源君不诚 @ 2017-08-06 22:14:39