打卡记录
方格取数（线性DP）
import sys
input = sys.stdin.readline
'''
输入样例：
8
2 3 13
2 6 6
3 5 7
4 4 14
5 2 21
5 6 4
6 3 15
7 2 14
0 0 0
输出样例：
67
'''
n = int(input())
w = [[0] * (n + 1) for _ in range(n + 1)]
while True:
a, b, c = map(int, input().split())
if a == 0 and b == 0 and c == 0:
break
w[a][b] = c
f = [[[0] * (n + 1) for _ in range(n + 1)] for _ in range(2 * n + 1)]
for k in range(2, 2 * n + 1):
for i1 in range(1, n + 1):
for i2 in range(1, n + 1):
j1, j2 = k - i1, k - i2
if 1 <= j1 <= n and 1 <= j2 <= n:
t = w[i1][j1]
if i1 != i2:
t += w[i2][j2]
f[k][i1][i2] = max(f[k - 1][i1][i2], f[k - 1][i1 - 1][i2], f[k - 1][i1][i2 - 1], f[k - 1][i1 - 1][i2]) + t
print(f[-1][-1][-1])
