CodeEff/ECCO huggingface dataset:
# Original solution
import sys
input = sys.stdin.buffer.readline
from collections import defaultdict
r,c,k = list(map(int,input().split()))
K = defaultdict(int)
for _ in range(k):
    x,y,z= [int(i) for i in input().split()]
    K[(x,y)] = z


dp = [[0]*(c+1) for _ in range(4)]
 
for i in range(1, r+1):
    for j in range(1, c+1):
        v = K[(i, j)]
        dp[0][j] = max(dp[0][j-1], dp[0][j], dp[1][j], dp[2][j], dp[3][j])
        dp[1][j] = max(dp[1][j-1], dp[0][j]+v) if v>0 else dp[1][j-1]
        dp[2][j] = max(dp[2][j-1], dp[1][j-1]+v) if v>0 else dp[2][j-1]
        dp[3][j] = max(dp[3][j-1], dp[2][j-1]+v) if v>0 else dp[3][j-1]
        
print((max(dp[i][-1] for i in range(4))))

# Optimized solution
import sys
input = sys.stdin.buffer.readline
H, W, K = list(map(int, input().split()))
B = {}
for _ in range(K):
    r, c, v = list(map(int, input().split()))
    B[(r, c)] = v

dp = [[0]*(W+1) for _ in range(4)]

for i in range(1, H+1):
    for j in range(1, W+1):
        if (i, j) in B:
            v = B[(i, j)]
            dp[0][j] = max(dp[0][j-1], dp[0][j], dp[1][j], dp[2][j], dp[3][j])
            dp[1][j] = max(dp[1][j-1], dp[0][j]+v)
            dp[2][j] = max(dp[2][j-1], dp[1][j-1]+v)
            dp[3][j] = max(dp[3][j-1], dp[2][j-1]+v)
        else:
            dp[0][j] = max(dp[0][j-1], dp[0][j], dp[1][j], dp[2][j], dp[3][j])
            dp[1][j] = dp[1][j-1]
            dp[2][j] = dp[2][j-1]
            dp[3][j] = dp[3][j-1]

print((max(dp[i][-1] for i in range(4))))
# Original solution
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def solve():
    def chmax(i, j, c, val):dp[i][j][c]=max(dp[i][j][c],val)

    dp = [[[-1] * 4 for _ in range(w+1)] for _ in range(h+1)]
    dp[0][0][0] = 0
    for i in range(h):
        for j in range(w):
            if aa[i][j]:
                for c in range(2,-1,-1):
                    pre = dp[i][j][c]
                    if pre==-1:continue
                    chmax(i,j,c+1,dp[i][j][c]+aa[i][j])
            for c in range(4):
                pre = dp[i][j][c]
                if pre == -1: continue
                chmax(i+1,j,0,pre)
                chmax(i,j+1,c,pre)

    ans = max(dp[h-1][w-1])
    print(ans)

h,w,k=MI()
aa=[[0]*w for _ in range(h)]
for _ in range(k):
    i,j,v=MI()
    aa[i-1][j-1]=v
solve()


# Optimized solution
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def solve():
    dp0 = [0] * (w + 1)
    dp1 = [0] * (w + 1)
    dp2 = [0] * (w + 1)
    dp3 = [0] * (w + 1)
    for i in range(h):
        for j in range(w):
            v = vv[i * w + j]
            if v:
                dp3[j] = max(dp3[j], dp2[j] + v)
                dp2[j] = max(dp2[j], dp1[j] + v)
                dp1[j] = max(dp1[j], dp0[j] + v)
            dp3[j + 1] = max(dp3[j + 1], dp3[j])
            dp2[j + 1] = max(dp2[j + 1], dp2[j])
            dp1[j + 1] = max(dp1[j + 1], dp1[j])
            dp0[j] = max(dp1[j], dp2[j], dp3[j])
    print(dp0[-2])

h, w, k = MI()
vv = [0] * h * w
for _ in range(k):
    i, j, v = MI()
    i, j = i - 1, j - 1
    vv[i * w + j] = v
solve()
# Original solution
import sys
import math
from collections import defaultdict
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(eval(input()))
NMI = lambda: list(map(int, input().split()))
NLI = lambda: list(NMI())
SI = lambda: eval(input())


def main():
    R, C, K = NMI()
    item = {(0,0):0}

    for i in range(K):
        r_, c_, v_, = NMI()
        item[(r_ - 1,c_ - 1)] = v_

    dp = [[[0 for _ in range(C + 2)] for _ in range(R + 2)] for _ in range(4)]

    for i in range(R + 1):
        for j in range(C + 1):
            for k in range(4):
                a = dp[k][i][j]
                if (i,j) in item:
                    v = item[(i,j)]
                else:
                    v = 0

                if k == 3:
                    dp[0][i + 1][j] = max(a, dp[0][i + 1][j])
                    continue
                dp[0][i + 1][j] = max(a, a + v, dp[0][i + 1][j])
                dp[k][i][j + 1] = max(a, dp[k][i][j + 1])
                dp[k + 1][i][j + 1] = max(a + v, dp[k + 1][i][j + 1])

    print((max(dp[0][R][C], dp[1][R][C], dp[2][R][C], dp[3][R][C])))

if __name__ == "__main__":
    main()

# Optimized solution
import sys
import math
from collections import defaultdict
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(eval(input()))
NMI = lambda: list(map(int, input().split()))
NLI = lambda: list(NMI())
SI = lambda: eval(input())


def main():
    R, C, K = NMI()
    item = [[0] * (C + 1) for i in range(R + 1)]

    for i in range(K):
        r_, c_, v_, = NMI()
        item[r_ - 1][c_ - 1] = v_

    dp = [[[0 for _ in range(C + 2)] for _ in range(R + 2)] for _ in range(4)]

    for i in range(R + 1):
        for j in range(C + 1):
            for k in range(4):
                a = dp[k][i][j]
                v = item[i][j]

                if k == 3:
                    dp[0][i + 1][j] = max(a, dp[0][i + 1][j])
                    continue
                dp[0][i + 1][j] = max(a, a + v, dp[0][i + 1][j])
                dp[k][i][j + 1] = max(a, dp[k][i][j + 1])
                dp[k + 1][i][j + 1] = max(a + v, dp[k + 1][i][j + 1])

    print((max(dp[0][R][C], dp[1][R][C], dp[2][R][C], dp[3][R][C])))

if __name__ == "__main__":
    main()
# Original solution
def max2(x,y):
    return x if x > y else y

R, C, K = list(map(int, input().split()))
V = [[0]*R for _ in range(C)]
for _ in range(K):
    r, c, v = list(map(int, input().split()))
    V[c-1][r-1] = v

dp = [[0]*4 for _ in range(R)]
for j in range(R):
    if V[0][j] != 0:
        dp[j][1] = max2(dp[j - 1][1], dp[j - 1][0]) + V[0][j]
    if j != 0:
        dp[j][0] = max2(dp[j - 1][1], dp[j - 1][0])
for i in range(1,C):
    for j in range(R):
        v = V[i][j]
        if v != 0:
            if dp[j][2] != 0:
                dp[j][3] = max2(dp[j][2] + v, dp[j][3])
            if dp[j][1] != 0:
                dp[j][2] = max2(dp[j][1] + v, dp[j][2])
            dp[j][1] = max2(v, dp[j][1])
        if j != 0:
            if v != 0:
                dp[j][1] = max2(max(dp[j - 1][k] for k in range(4)) + v, dp[j][1])
            dp[j][0] = max2(max(dp[j - 1][k] for k in range(4)), dp[j][0])
print((max(dp[-1])))


# Optimized solution
R, L, K = list(map(int, input().split()))
V = [[0]*R for _ in range(L)]
for _ in range(K):
    r, c, v = list(map(int, input().split()))
    V[c-1][r-1] = v
A, B, C, D = [[0]*(R+1) for _ in range(4)]
for i in range(L):
    for j in range(R):
        A[j] = max(A[j-1], B[j-1], C[j-1], D[j-1])
        v = V[i][j]
        if v != 0:
            D[j], C[j], B[j] = max(C[j] + v, D[j]), max(B[j] + v, C[j]), max(A[j] + v, B[j])

print((max(A[-2], B[-2], C[-2], D[-2])))
# Original solution
def max2(x,y):
    return x if x > y else y

R, L, K = list(map(int, input().split()))
V = [[0]*R for _ in range(L)]
for _ in range(K):
    r, c, v = list(map(int, input().split()))
    V[c-1][r-1] = v
A, B, C, D = [[0]*(R+1) for _ in range(4)]
for i in range(L):
    for j in range(R):
        A[j] = max(A[j-1], B[j-1], C[j-1], D[j-1])
        v = V[i][j]
        if v != 0:
            D[j], C[j], B[j] = max2(C[j] + v, D[j]), max2(B[j] + v, C[j]), max2(A[j] + v, B[j])

print((max(A[-2], B[-2], C[-2], D[-2])))

# Optimized solution
import sys
input = sys.stdin.readline
R, L, K = list(map(int, input().split()))
V = [[0]*R for _ in range(L)]
for _ in range(K):
    r, c, v = list(map(int, input().split()))
    V[c-1][r-1] = v
A, B, C, D = [[0]*(R+1) for _ in range(4)]
for i in range(L):
    for j in range(R):
        A[j] = max(A[j-1],B[j-1],C[j-1],D[j-1])
        v = V[i][j]
        if v != 0:
            D[j], C[j], B[j] = max(C[j]+v,D[j]), max(B[j]+v,C[j]), max(A[j]+v,B[j])
print((max(A[-2],B[-2],C[-2],D[-2])))
# Original solution
r,c,k = list(map(int,input().split()))
l = [[0]*c for i in range(r)]

for i in range(k):
    x,y,v = list(map(int,input().split()))
    l[x-1][y-1] = v

dp = [[[0]*4 for i in range(c+1)] for j in range(r+1)]

for i in range(r):
    for j in range(c):
        if l[i][j] > 0:
            v = l[i][j]
            dp[i+1][j+1][0] = max(max(dp[i][j+1]),dp[i+1][j][0])
            dp[i+1][j+1][1] = max(max(dp[i][j+1])+v,dp[i+1][j][0]+v,dp[i+1][j][1])
            dp[i+1][j+1][2] = max(dp[i+1][j][1]+v,dp[i+1][j][2])
            dp[i+1][j+1][3] = max(dp[i+1][j][2]+v,dp[i+1][j][3])
        else:
            dp[i+1][j+1][0] = max(max(dp[i][j+1]),dp[i+1][j][0])
            dp[i+1][j+1][1] = dp[i+1][j][1]
            dp[i+1][j+1][2] = dp[i+1][j][2]
            dp[i+1][j+1][3] = dp[i+1][j][3]
print((max(dp[-1][-1])))

# Optimized solution
import sys
input = sys.stdin.readline
r,c,k = list(map(int,input().split()))
l = [[0]*c for i in range(r)]

for i in range(k):
    x,y,v = list(map(int,input().split()))
    l[x-1][y-1] = v

dp = [[[0]*4 for i in range(c+1)] for j in range(r+1)]

for i in range(r):
    for j in range(c):
        M = max(dp[i][j+1])
        if l[i][j] > 0:
            v = l[i][j]
            dp[i+1][j+1][0] = max(M,dp[i+1][j][0])
            dp[i+1][j+1][1] = max(M+v,dp[i+1][j][0]+v,dp[i+1][j][1])
            dp[i+1][j+1][2] = max(dp[i+1][j][1]+v,dp[i+1][j][2])
            dp[i+1][j+1][3] = max(dp[i+1][j][2]+v,dp[i+1][j][3])
        else:
            dp[i+1][j+1][0] = max(M,dp[i+1][j][0])
            dp[i+1][j+1][1] = dp[i+1][j][1]
            dp[i+1][j+1][2] = dp[i+1][j][2]
            dp[i+1][j+1][3] = dp[i+1][j][3]
print((max(dp[-1][-1])))
# Original solution
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
def main():
    R, C, K = list(map(int, input().split()))
    D = [[*list(map(int, input().split()))] for _ in [None] * K]
    D = {(r - 1, c - 1) : v for r, c, v in D}

    dp = [[[-1] * 4 for _ in [None] * C] for _ in [None] * R]

    dp[0][0][0] = 0
    for r in range(R):
        for c in range(C):
            v = D.get((r, c), None)
            for i in range(4):
                if dp[r][c][i] > -1:
                    if r < R - 1:
                        dp[r + 1][c][0] = max(dp[r + 1][c][0], dp[r][c][i])
                    if c < C - 1:
                        dp[r][c + 1][i] = max(dp[r][c + 1][i], dp[r][c][i])
                    if i < 3 and v:
                        if r < R - 1:
                            dp[r + 1][c][0] = max(dp[r + 1][c][0], dp[r][c][i] + v)
                        if c < C - 1:
                            dp[r][c + 1][i + 1] = max(dp[r][c + 1][i + 1], dp[r][c][i] + v)

    v = D.get((R - 1, C - 1), 0)
    ans = dp[R - 1][C - 1][3]
    for i in range(3):
        ans = max(ans, dp[R - 1][C - 1][i] + v)
    print(ans)

if __name__ == "__main__":
    main()

# Optimized solution
import sys

def solve():
    input = sys.stdin.readline
    R, C, K = list(map(int, input().split()))
    item = [[0 for _ in range(C)] for r in range(R)]
    for _ in range(K):
        r, c, k = list(map(int, input().split()))
        item[r-1][c-1] = k
    
    DP = [[[-1 for _ in range(C)] for r in range(R)] for i in range(4)]
    DP[0][0][0] = 0
    for r in range(R):
        for c in range(C):
            for i in range(4):
                if DP[i][r][c] > -1:
                    if r + 1 < R: 
                        DP[0][r+1][c] = max(DP[0][r+1][c], DP[i][r][c])
                    if c + 1 < C: 
                        DP[i][r][c+1] = max(DP[i][r][c+1], DP[i][r][c])
                    if i < 3 and item[r][c] > 0:
                        if r + 1 < R: DP[0][r+1][c] = max(DP[0][r+1][c], DP[i][r][c] + item[r][c])
                        if c + 1 < C: DP[i+1][r][c+1] = max(DP[i+1][r][c+1], DP[i][r][c] + item[r][c])

    ans = DP[3][R-1][C-1]
    for i in range(3): ans = max(ans, DP[i][R-1][C-1] + item[R-1][C-1])
    print(ans)
    return 0

if __name__ == "__main__":
    solve()
# Original solution
#!/usr/bin/env python3
def main():
    (R, C, K), *D = [[*list(map(int,o.split()))] for o in open(0)]
    D = {(r - 1, c - 1) : v for r, c, v in D}

    dp = [[[-1] * C for _ in [None] * R] for _ in [None] * 4]

    dp[0][0][0] = 0
    for r in range(R):
        for c in range(C):
            v = D.get((r, c), None)
            for i in range(4):
                if dp[i][r][c] > -1:
                    if r < R - 1:
                        dp[0][r + 1][c] = max(dp[0][r + 1][c], dp[i][r][c])
                    if c < C - 1:
                        dp[i][r][c + 1] = max(dp[i][r][c + 1], dp[i][r][c])
                    if i < 3 and v:
                        if r < R - 1:
                            dp[0][r + 1][c] = max(dp[0][r + 1][c], dp[i][r][c] + v)
                        if c < C - 1:
                            dp[i + 1][r][c + 1] = max(dp[i + 1][r][c + 1], dp[i][r][c] + v)

    v = D.get((R - 1, C - 1), 0)
    ans = dp[3][R - 1][C - 1]
    for i in range(3):
        ans = max(ans, dp[i][R - 1][C - 1] + v)
    print(ans)

if __name__ == "__main__":
    main()

# Optimized solution
#!/usr/bin/env python3
import sys
input = sys.stdin.readline

def main():
    R, C, K = list(map(int, input().split()))
    D = {}
    for _ in [None] * K:
        r, c, v = list(map(int, input().split()))
        D[(r - 1, c - 1)] = v

    dp = [[[-1] * C for _ in [None] * R] for _ in [None] * 4]

    dp[0][0][0] = 0
    for r in range(R):
        for c in range(C):
            v = D.get((r, c), None)
            for i in range(4):
                if dp[i][r][c] > -1:
                    if r < R - 1:
                        dp[0][r + 1][c] = max(dp[0][r + 1][c], dp[i][r][c])
                    if c < C - 1:
                        dp[i][r][c + 1] = max(dp[i][r][c + 1], dp[i][r][c])
                    if i < 3 and v:
                        if r < R - 1:
                            dp[0][r + 1][c] = max(dp[0][r + 1][c], dp[i][r][c] + v)
                        if c < C - 1:
                            dp[i + 1][r][c + 1] = max(dp[i + 1][r][c + 1], dp[i][r][c] + v)

    v = D.get((R - 1, C - 1), 0)
    ans = dp[3][R - 1][C - 1]
    for i in range(3):
        ans = max(ans, dp[i][R - 1][C - 1] + v)
    print(ans)

if __name__ == "__main__":
    main()
# Original solution
import bisect
import collections
import copy
import functools
import heapq
import math
import sys
from collections import deque
from collections import defaultdict
input = sys.stdin.readline
sys.setrecursionlimit(10**9)
MOD = 10**9+7

R,C,K = list(map(int,input().split()))

item = [[0]*C for _ in range(R)]
for i in range(K):
    r,c,v = list(map(int,input().split()))
    item[r-1][c-1] = v
#print(item)

dp = [[[0]*4 for _ in range(C)] for _ in range(R)]

for i in range(R):
    for j in range(C):
        for k in range(1,4):
            #print(i,j,k)
            if k == 1:
                if i != 0:
                    if j != 0:
                        dp[i][j][k] = max(dp[i][j-1][k], dp[i][j-1][k-1] + item[i][j], max(dp[i-1][j]) + item[i][j])
                    else:
                        dp[i][j][k] = max(0, 0 + item[i][j], max(dp[i-1][j]) + item[i][j])
                else:
                    if j != 0:
                        dp[i][j][k] = max(dp[i][j-1][k], dp[i][j-1][k-1] + item[i][j])
                    else:
                        dp[i][j][k] = max(0, 0 + item[i][j])


            else:
                if j != 0:
                    dp[i][j][k] = max(dp[i][j-1][k], dp[i][j-1][k-1] + item[i][j])
                else:
                    dp[i][j][k] = max(0, 0 + item[i][j])

            #print(dp)
print((max(dp[R-1][C-1])))

# Optimized solution
import bisect
import collections
import copy
import functools
import heapq
import math
import sys
from collections import deque
from collections import defaultdict
input = sys.stdin.readline
sys.setrecursionlimit(10**9)
MOD = 10**9+7

R,C,K = list(map(int,input().split()))

item = [[0]*C for _ in range(R)]
for i in range(K):
    r,c,v = list(map(int,input().split()))
    item[r-1][c-1] = v
#print(item)

dp = [[0]*4 for _ in range(C)]
preview = [[0]*4 for _ in range(C)]

for i in range(R):
    for j in range(C):
        for k in range(1,4):
            #print(i,j,k)
            if k == 1:
                if i != 0:
                    if j != 0:
                        dp[j][k] = max(dp[j-1][k], dp[j-1][k-1] + item[i][j], max(preview[j]) + item[i][j])
                    else:
                        dp[j][k] = max(0, 0 + item[i][j], max(preview[j]) + item[i][j])
                else:
                    if j != 0:
                        dp[j][k] = max(dp[j-1][k], dp[j-1][k-1] + item[i][j])
                    else:
                        dp[j][k] = max(0, 0 + item[i][j])


            else:
                if j != 0:
                    dp[j][k] = max(dp[j-1][k], dp[j-1][k-1] + item[i][j])
                else:
                    dp[j][k] = max(0, 0 + item[i][j])

            #print(dp)
    preview = dp
print((max(dp[C-1])))
# Original solution
def main():
    import sys
    from copy import deepcopy
    input = sys.stdin.readline
    R, C, K = [int(x) for x in input().strip().split()]
    G = [[0] * (C+1) for r in range(R+1)]
    for k in range(K):
        r, c, v = [int(x) for x in input().strip().split()]
        G[r][c] = v
    # for r in range(R+1):
    #     print(G[r])
    ans = [[[0] * 4 for _ in range(C+1)] for _ in range(R+1)]
    for r in range(1, R+1):
        for c in range(1, C+1):
            ans[r][c][0] = max(ans[r-1][c][-1], ans[r][c-1][0])
            for i in range(1, 4):
                ans[r][c][i] = max(ans[r-1][c][3], ans[r][c-1][i], ans[r-1][c][3]+G[r][c], ans[r][c-1][i-1]+G[r][c])

    print((max(ans[-1][-1])))

if __name__ == '__main__':
    main()


# Optimized solution
def main():
    import sys
    from copy import deepcopy
    input = sys.stdin.readline
    R, C, K = [int(x) for x in input().strip().split()]
    G = [[0] * (C+1) for r in range(R+1)]
    for k in range(K):
        r, c, v = [int(x) for x in input().strip().split()]
        G[r][c] = v
    # for r in range(R+1):
    #     print(G[r])
    ans = [[[0] * 4 for _ in range(C+1)] for _ in range(2)]
    for r in range(1, R+1):
        for c in range(1, C+1):
            ans[r%2][c][0] = max(ans[(r-1)%2][c][-1], ans[r%2][c-1][0])
            for i in range(1, 4):
                ans[r%2][c][i] = max(ans[(r-1)%2][c][3], ans[r%2][c-1][i], ans[(r-1)%2][c][3]+G[r][c], ans[r%2][c-1][i-1]+G[r][c])

    print((max(ans[R%2][-1])))

if __name__ == '__main__':
    main()
# Original solution
R,C,K = list(map(int,input().split()))
board = [[0 for _ in range(C)] for __ in range(R)]
for _ in range(K):
  r,c,v = list(map(int,input().split()))
  board[r-1][c-1] = v

dp = [[[0 for _ in range(C)] for __ in range(R)] for ___ in range(4)]
ans = 0
for i in range(R):
  for j in range(C):
    dp[1][i][j] = max(dp[1][i][j],dp[0][i][j]+board[i][j])
    for k in range(4):
      if j>0:
        dp[k][i][j] = max(dp[k][i][j],dp[k][i][j-1])
      if j>0 and k>0:
        dp[k][i][j] = max(dp[k][i][j],dp[k-1][i][j-1]+board[i][j])
      if i>0:
        dp[0][i][j] = max(dp[0][i][j],dp[k][i-1][j])
        dp[1][i][j] = max(dp[1][i][j],dp[k][i-1][j]+board[i][j])
      ans = max(ans,dp[k][i][j])
#print(*board,sep='\n')
#print(*dp,sep='\n')
print(ans)

# Optimized solution
R,C,K = list(map(int,input().split()))
board = [[0 for _ in range(C)] for __ in range(R)]
for _ in range(K):
  r,c,v = list(map(int,input().split()))
  board[r-1][c-1] = v

dp0 = [[0]*C for _ in range(R)]
dp1 = [[0]*C for _ in range(R)]
dp2 = [[0]*C for _ in range(R)]
dp3 = [[0]*C for _ in range(R)]

ans = 0
for i in range(R):
  for j in range(C):
    if dp1[i][j] < dp0[i][j]+board[i][j]:
      dp1[i][j] = dp0[i][j]+board[i][j]
    if j>0:
      if dp0[i][j] < dp0[i][j-1]:
        dp0[i][j] = dp0[i][j-1]
      if dp1[i][j] < dp1[i][j-1]:
        dp1[i][j] = dp1[i][j-1]
      if dp2[i][j] < dp2[i][j-1]:
        dp2[i][j] = dp2[i][j-1]
      if dp3[i][j] < dp3[i][j-1]:
        dp3[i][j] = dp3[i][j-1]
      if dp1[i][j] < dp0[i][j-1]+board[i][j]:
        dp1[i][j] = dp0[i][j-1]+board[i][j]
      if dp2[i][j] < dp1[i][j-1]+board[i][j]:
        dp2[i][j] = dp1[i][j-1]+board[i][j]
      if dp3[i][j] < dp2[i][j-1]+board[i][j]:
        dp3[i][j] = dp2[i][j-1]+board[i][j]
    if i>0:
      if dp0[i][j] < dp0[i-1][j]:
        dp0[i][j] = dp0[i-1][j]
      if dp0[i][j] < dp1[i-1][j]:
        dp0[i][j] = dp1[i-1][j]
      if dp0[i][j] < dp2[i-1][j]:
        dp0[i][j] = dp2[i-1][j]
      if dp0[i][j] < dp3[i-1][j]:
        dp0[i][j] = dp3[i-1][j]
      if dp1[i][j] < dp0[i-1][j]+board[i][j]:
        dp1[i][j] = dp0[i-1][j]+board[i][j]
      if dp1[i][j] < dp1[i-1][j]+board[i][j]:
        dp1[i][j] = dp1[i-1][j]+board[i][j]
      if dp1[i][j] < dp2[i-1][j]+board[i][j]:
        dp1[i][j] = dp2[i-1][j]+board[i][j]
      if dp1[i][j] < dp3[i-1][j]+board[i][j]:
        dp1[i][j] = dp3[i-1][j]+board[i][j]
print((max(dp0[-1][-1],dp1[-1][-1],dp2[-1][-1],dp3[-1][-1])))
# Original solution
R,C,K=list(map(int,input().split()))
value=[[0]*(C+1) for i in range(R+1)]
for i in range(K):
  r,c,v=list(map(int,input().split()))
  value[r][c]=v
DP0=[[0]*(C+1) for i in range(R+1)]
DP1=[[0]*(C+1) for i in range(R+1)]
DP2=[[0]*(C+1) for i in range(R+1)]
DP3=[[0]*(C+1) for i in range(R+1)]
for i in range(1,R+1):
  for j in range(1,C+1):
    v=value[i][j]
    DP0[i][j]=max(DP0[i][j-1],DP1[i-1][j],DP2[i-1][j],DP3[i-1][j])
    DP1[i][j]=max(DP0[i-1][j]+v,DP1[i-1][j]+v,DP2[i-1][j]+v,
                  DP3[i-1][j]+v,DP1[i][j-1],DP0[i][j-1]+v)
    DP2[i][j]=max(DP1[i][j-1]+v,DP2[i][j-1])
    DP3[i][j]=max(DP2[i][j-1]+v,DP3[i][j-1])

    
print((max(DP0[R][C],DP1[R][C],DP2[R][C],DP3[R][C])))

# Optimized solution
R,C,K=list(map(int,input().split()))
value=[[0]*(C+1) for i in range(R+1)]
for i in range(K):
  r,c,v=list(map(int,input().split()))
  value[r][c]=v
DP0=[[0]*(C+1) for i in range(R+1)]
DP1=[[0]*(C+1) for i in range(R+1)]
DP2=[[0]*(C+1) for i in range(R+1)]
DP3=[[0]*(C+1) for i in range(R+1)]
for i in range(1,R+1):
  for j in range(1,C+1):
    v=value[i][j]
    a=DP0[i][j-1]
    b=DP1[i][j-1]
    c=DP1[i-1][j]
    d=DP2[i-1][j]
    e=DP3[i-1][j]
    f=DP2[i][j-1]
    DP0[i][j]=max(a,c,d,e)
    DP1[i][j]=max(DP0[i-1][j]+v,c+v,d+v,e+v,b,a+v)
    DP2[i][j]=max(b+v,f)
    DP3[i][j]=max(f+v,DP3[i][j-1])

print((max(DP0[R][C],DP1[R][C],DP2[R][C],DP3[R][C])))
# Original solution
r,c,k=list(map(int,input().split()))
P=[[0 for i in range(c+1)] for q in range(r+1)]

for i in range(k):
    nr,nc,nv=list(map(int,input().split()))
    #nr,nc,nv=map(int,inp[i].split())
    #T[nr].append((nc,nv))
    P[nr][nc]=nv

dp=[[[0,0,0,0] for i in range(c+1)] for q in range(r+1)]

for i in range(1,r+1):
    head=0
    for q in range(1,c+1):
        pri=P[i][q]
        dp[i][q][0]=max(max(dp[i-1][q]),dp[i][q-1][0])
        dp[i][q][1]=dp[i][q][0]+pri
        dp[i][q][3]=max(dp[i][q-1][3],dp[i][q-1][2]+pri)
        dp[i][q][2]=max(dp[i][q-1][2],dp[i][q-1][1]+pri)
        dp[i][q][1]=max(dp[i][q-1][1],dp[i][q-1][0]+pri,dp[i][q][1])

print((max(dp[-1][-1])))


# Optimized solution
r,c,k=list(map(int,input().split()))
P=[[0 for i in range(c+1)] for q in range(r+1)]

for i in range(k):
    nr,nc,nv=list(map(int,input().split()))
    #nr,nc,nv=map(int,inp[i].split())
    #T[nr].append((nc,nv))
    P[nr][nc]=nv

dp=[[[0,0,0,0] for i in range(c+1)] for q in range(r+1)]

for i in range(1,r+1):
    for q in range(1,c+1):
        pri=P[i][q]
        dp[i][q][0]=max(dp[i-1][q][3],dp[i][q-1][0])
        dp[i][q][1]=max(dp[i][q-1][1],dp[i][q-1][0]+pri,dp[i][q][0]+pri)
        dp[i][q][2]=max(dp[i][q-1][2],dp[i][q-1][1]+pri,dp[i][q][1])
        dp[i][q][3]=max(dp[i][q-1][3],dp[i][q-1][2]+pri,dp[i][q][2])

print((max(dp[-1][-1])))