蒟蒻不会DP，所以这到题目第一思路就是DFS。两遍DFS（嵌套DFS）时间复杂度巨高（$2^{n*n*2^{n*n}}$），本以为这题n <= 9所以程序能狗过，，有没有大佬可以帮忙剪枝，降低一下算法的时间复杂度呀（总感觉能过，但是本蒟蒻不会理直气壮）

using namespace std;
int n;
int sum;
int Max,Max_1;
int len;
int path[12][12];
int st[12][12];
int st_1[12][12];
int st_2[12][12];
int dx[2] = {0,1};
int dy[2] = {1,0};

struct Node
{
    int x;
    int y;
}node[15];

void DFS_1(int x,int y,int cnt)
{
    if(x == n && y == n)
    {
        Max_1 = max(Max_1,cnt);
    }
    else
    {
        if(x == 1 && y == 1)
            Max_1 = 0;
        for(int i = 0;i < 2;i++)
        {
            int xx = x + dx[i],yy = y + dy[i];
            if(!st_2[xx][yy] && xx <= n && yy <= n)
            {
                st_2[xx][yy] = 1;
                if(st_1[xx][yy])    DFS_1(xx,yy,cnt);
                else                DFS_1(xx,yy,cnt+path[xx][yy]);
                st_2[xx][yy] = 0;
            }
        }
    }
}

void DFS(int x,int y,int cnt)
{
    if(x == n && y == n)
    {
        memset(st_1,0,sizeof(st_1));
        for(int i = 0;i < len;i++)
            st_1[node[i].x][node[i].y] = 1;

        DFS_1(1,1,0);
        Max = max(Max,cnt+Max_1);
        return;
    }
    else
    {
        for(int i = 0;i < 2;i++)
        {
            int xx = x + dx[i],yy = y + dy[i];
            if(!st[xx][yy] && xx <= n && yy <= n)
            {
                st[xx][yy] = 1;
                node[len].x = xx;
                node[len++].y = yy;
                DFS(xx,yy,cnt+path[xx][yy]);
                node[--len].x = 0;
                node[len].y = 0;
                st[xx][yy] = 0;
            }
        }
    }
}

int main()
{
    cin >> n;
    int x,y,m;

    while(cin >> x >> y >> m)
    {
        if(!x && !y && !m)
            break;
        path[x][y] = m;
    }

    DFS(1,1,path[1][1]);
    cout << Max;
    return 0;
}