CodeEff/ECCO huggingface dataset:
# Original solution
def main():
  import sys
  input=sys.stdin.readline
  h,w,k=list(map(int,input().split()))
  H=list(range(h))
  W=list(range(w))
  dp=[[[0]*4 for j in W] for i in H]
  for _ in range(k):
    r,c,v=list(map(int,input().split()))
    dp[r-1][c-1][0]=v
  if dp[0][0][0]!=0:
    dp[0][0][1]=dp[0][0][0]
    dp[0][0][0]=0
  for y in H:
    for x in W:
      v=dp[y][x][0]
      dp[y][x][0]=0
      for i in range(4):
        if 0<x:
          if dp[y][x][i]<dp[y][x-1][i]:
            dp[y][x][i]=dp[y][x-1][i]
          if 0<i and v!=0 and dp[y][x][i]<dp[y][x-1][i-1]+v:
            dp[y][x][i]=dp[y][x-1][i-1]+v
        if 0<y:
          if dp[y][x][0]<dp[y-1][x][i]:
            dp[y][x][0]=dp[y-1][x][i]
          if v!=0 and dp[y][x][1]<dp[y-1][x][i]+v:
            dp[y][x][1]=dp[y-1][x][i]+v
  print((max(dp[h-1][w-1])))
main()

# Optimized solution
def main():
  import sys
  input=sys.stdin.readline
  h,w,k=list(map(int,input().split()))
  H=list(range(h))
  W=list(range(w))
  dp=[[[0]*w for j in H] for i in range(4)]
  for _ in range(k):
    r,c,v=list(map(int,input().split()))
    dp[0][r-1][c-1]=v
  if dp[0][0][0]!=0:
    dp[1][0][0]=dp[0][0][0]
    dp[0][0][0]=0
  for y in H:
    for x in W:
      v=dp[0][y][x]
      dp[0][y][x]=0
      for i in range(4):
        if 0<x:
          if dp[i][y][x]<dp[i][y][x-1]:
            dp[i][y][x]=dp[i][y][x-1]
          if 0<i and v!=0 and dp[i][y][x]<dp[i-1][y][x-1]+v:
            dp[i][y][x]=dp[i-1][y][x-1]+v
        if 0<y:
          if dp[0][y][x]<dp[i][y-1][x]:
            dp[0][y][x]=dp[i][y-1][x]
          if v!=0 and dp[1][y][x]<dp[i][y-1][x]+v:
            dp[1][y][x]=dp[i][y-1][x]+v
  print((max([dp[i][h-1][w-1] for i in range(4)])))
main()
# Original solution
R, C, K = list(map(int, input().split()))
V = [[0] * (C + 1) for _ in range(R + 1)]
for _ in range(K):
    r, c, v = list(map(int, input().split()))
    V[r][c] = v

X = [[[0] * 4 for _ in range(C + 1)] for _ in range(R + 1)]
for i in range(1, R + 1):
    for j in range(1, C + 1):
        X[i][j][0] = max(X[i-1][j][0], X[i-1][j][1], X[i-1][j][2], X[i-1][j][3], X[i][j-1][0])
        X[i][j][1] = max(X[i][j][0] + V[i][j], X[i][j-1][1])
        X[i][j][2] = max(X[i][j-1][1] + V[i][j], X[i][j-1][2])
        X[i][j][3] = max(X[i][j-1][2] + V[i][j], X[i][j-1][3])

print((max(X[R][C])))

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

X = [[[0] * 4 for _ in range(C + 1)] for _ in range(R + 1)]
for i in range(1, R + 1):
    Xi = X[i]
    Xi1 = X[i-1]
    Vi = V[i]
    for j in range(1, C + 1):
        Vij = Vi[j]
        Xij = Xi[j]
        Xij1 = Xi[j-1]
        Xij[0] = max(max(Xi1[j]), Xij1[0])
        Xij[1] = max(Xij[0] + Vij, Xij1[1])
        Xij[2] = max(Xij1[1] + Vij, Xij1[2])
        Xij[3] = max(Xij1[2] + Vij, Xij1[3])

print((max(X[R][C])))
# Original solution
R, C, K = list(map(int, input().split()))
V = [[0] * (C + 1) for _ in range(R + 1)]
for _ in range(K):
    r, c, v = list(map(int, input().split()))
    V[r][c] = v

X = [[[0] * 4 for _ in range(C + 1)] for _ in range(R + 1)]
for i in range(1, R + 1):
    Xi = X[i]
    Xi1 = X[i-1]
    Vi = V[i]
    for j in range(1, C + 1):
        Vij = Vi[j]
        Xij = Xi[j]
        Xij1 = Xi[j-1]
        Xij[0] = max(max(Xi1[j]), Xij1[0])
        Xij[1] = max(Xij[0] + Vij, Xij1[1])
        Xij[2] = max(Xij1[1] + Vij, Xij1[2])
        Xij[3] = max(Xij1[2] + Vij, Xij1[3])

print((max(X[R][C])))

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

X = [[0] * 4 for _ in range(R + 1)]
for i in range(1, C + 1):
    Vi = V[i]
    for j in range(1, R + 1):
        v = Vi[j]
        Xj = X[j]
        if v:
            Xj[3] = max(Xj[3], Xj[2] + v)
            Xj[2] = max(Xj[2], Xj[1] + v)
            Xj[0] = max(Xj[0], max(X[j-1]))
            Xj[1] = max(Xj[1], Xj[0] + v)
        else:
            Xj[0] = max(Xj[0], max(X[j-1]))

print((max(X[R])))
# Original solution
import sys

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

dp = [[[0]*4 for _ in range(C)] for _ in range(R+1)] # [r, c, とったアイテム]のvの最大値

for r in range(R-1, -1, -1):
    dp[r][C - 1][0] = dp[r + 1][C - 1][3]
    for i in range(1, 4):
        dp[r][C-1][i] = dp[r + 1][C-1][3]+values[r][C-1]
    for c in range(C-2, -1, -1):
        v = values[r][c]
        for i in range(4):
            if i == 0 or v==0:
                dp[r][c][i] = max([dp[r+1][c][3], dp[r][c+1][i]])
            else:
                dp[r][c][i] = max([dp[r + 1][c][3]+v, dp[r][c + 1][i], dp[r][c + 1][i-1] + v])

print((dp[0][0][3]))


# Optimized solution
import sys

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

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

for r in range(R-1, -1, -1):
    # dp[0][r][C - 1] = dp[3][r + 1][C - 1]
    # for i in range(1, 4):
    #    dp[i][r][C-1] = dp[3][r + 1][C-1][3]+values[r][C-1]
    for c in range(C-1, -1, -1):
        v = values[r][c]
        for i in range(4):
            if i == 0 or v == 0:
                dp[i][r][c] = max(dp[3][r+1][c], dp[i][r][c+1])
            else:
                dp[i][r][c] = max(dp[3][r + 1][c]+v, dp[i][r][c + 1], dp[i-1][r][c + 1] + v)

print((dp[3][0][0]))
# Original solution
import sys
import math
import collections
import bisect
import itertools

# import numpy as np

sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline().rstrip())
ns = lambda: list(map(int, sys.stdin.readline().rstrip().split()))
na = lambda: list(map(int, sys.stdin.readline().rstrip().split()))
na1 = lambda: list([int(x) - 1 for x in sys.stdin.readline().rstrip().split()])


# ===CODE===

def main():
    r, c, k = ns()

    mat = [[0 for _ in range(c + 1)] for __ in range(r + 1)]
    for _ in range(k):
        x, y, v = ns()
        x, y = x - 1, y - 1
        mat[x][y] = v

    dp = [[[0 for ___ in range(4)] for _ in range(c + 1)] for __ in range(r + 1)]

    for i in range(r):
        for j in range(c):
            for n in range(2, -1, -1):
                dp[i][j][n + 1] = max(dp[i][j][n + 1], dp[i][j][n] + mat[i][j])

            dp[i + 1][j][0] = max(dp[i][j])
            for n in range(4):
                dp[i][j + 1][n] = max(dp[i][j + 1][n], dp[i][j][n])

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


if __name__ == '__main__':
    main()


# Optimized solution
import sys
import math
import collections
import bisect
import itertools

# import numpy as np

sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline().rstrip())
ns = lambda: list(map(int, sys.stdin.readline().rstrip().split()))
na = lambda: list(map(int, sys.stdin.readline().rstrip().split()))
na1 = lambda: list([int(x) - 1 for x in sys.stdin.readline().rstrip().split()])


# ===CODE===

def main():
    r, c, k = ns()

    mat = [[0 for _ in range(c + 1)] for __ in range(r + 1)]
    for _ in range(k):
        x, y, v = ns()
        x, y = x - 1, y - 1
        mat[x][y] = v

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

    for i in range(r):
        ndp = [[0] * 4 for _ in range(c + 1)]
        for j in range(c):
            for n in range(2, -1, -1):
                dp[j][n + 1] = max(dp[j][n + 1], dp[j][n] + mat[i][j])

            ndp[j][0] = max(dp[j])
            for n in range(4):
                dp[j + 1][n] = max(dp[j + 1][n], dp[j][n])
        dp = ndp

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


if __name__ == '__main__':
    main()
# Original solution
import sys
input = lambda: sys.stdin.readline().rstrip()
inpl = lambda: list(map(int,input().split()))
R, C, K = inpl()
val = [[0]*(C+1) for r in range(R+1)]
for _ in range(K):
    r, c, v = inpl()
    val[r][c] = v

score = [[[0]*4 for c in range(C+1)] for r in range(R+1)]
for r in range(1,R+1):
    for c in range(1,C+1):
        for n in range(4):
            if n == 0:
                score[r][c][0] = max(max(score[r-1][c]), score[r][c-1][0])
            elif val[r][c] == 0:
                score[r][c][n] = score[r][c-1][n]
            elif n == 1:
                score[r][c][1] = max(max(score[r-1][c])+val[r][c],
                                     score[r][c-1][0]+val[r][c],
                                     score[r][c-1][1]) 
            else:
                score[r][c][n] = max(score[r][c-1][n-1]+val[r][c],
                                     score[r][c-1][n])

print((max(score[R][C])))


# Optimized solution
import sys
input = lambda: sys.stdin.readline().rstrip()
inpl = lambda: list(map(int,input().split()))
R, C, K = inpl()
N = 3
val = [[0]*(C+1) for r in range(R+1)]
for _ in range(K):
    r, c, v = inpl()
    val[r][c] = v

score = [[[0]*(N+1) for c in range(C+1)] for r in range(R+1)]
for r in range(1,R+1):
    for c in range(1,C+1):
        for n in range(N+1):
            if n == 0:
                score[r][c][0] = max(score[r-1][c][-1], score[r][c-1][0])
            elif val[r][c] == 0:
                score[r][c][n] = max(score[r][c-1][n],score[r][c][n-1])
            elif n == 1:
                score[r][c][1] = max(score[r-1][c][-1]+val[r][c],
                                     score[r][c-1][0]+val[r][c],
                                     score[r][c-1][1],
                                     score[r][c][0])
            else:
                score[r][c][n] = max(score[r][c-1][n-1]+val[r][c],
                                     score[r][c-1][n],
                                     score[r][c][n-1])

print((score[R][C][-1]))
# Original solution
import sys
input=sys.stdin.readline

R,C,K=list(map(int,input().split()))
rcv=[tuple(map(int,input().split())) for _ in range(K)]

MAP=[[0 for _ in range(C+2)] for _ in range(R+2)]
DP=[[[0 for _ in range(3)] for _ in range(C+2)] for _ in range(R+2)]
for r,c,v in rcv:
    MAP[r-1][c-1]=v

for i in range(R):
    for j in range(C):
        for k in range(3):
            if k==0:
                DP[i][j][k]=max(DP[i][j-1][k],DP[i-1][j][k]+MAP[i][j],
                                DP[i-1][j][k+1]+MAP[i][j],
                                DP[i-1][j][k+2]+MAP[i][j])
            else:
                DP[i][j][k]=max(DP[i][j-1][k],DP[i][j-1][k-1]+MAP[i][j])

ans=0
for i in range(R):
    for j in range(C):
        ans=max(ans,max(DP[i][j]))
print(ans)

# Optimized solution
import sys
input = sys.stdin.readline

R,C,K=list(map(int,input().split()))
J=[tuple(map(int,input().split())) for i in range(K)]

#DP0=[[0]*(C+2) for i in range(R+2)]
DP1=[[0]*(C+2) for i in range(R+2)]
DP2=[[0]*(C+2) for i in range(R+2)]
DP3=[[0]*(C+2) for i in range(R+2)]

MAP=[[0]*C for i in range(R)]

for x,y,v in J:
    MAP[x-1][y-1]=v

for i in range(R):
    for j in range(C):
        DP1[i][j]=max(DP1[i][j-1],DP1[i-1][j]+MAP[i][j],DP2[i-1][j]+MAP[i][j],DP3[i-1][j]+MAP[i][j])
        DP2[i][j]=max(DP2[i][j-1],DP1[i][j-1]+MAP[i][j])
        DP3[i][j]=max(DP3[i][j-1],DP2[i][j-1]+MAP[i][j])

ANS=0
for i in range(R):
    for j in range(C):
        ANS=max(ANS,DP1[i][j],DP2[i][j],DP3[i][j])
print(ANS)
# Original solution
R,C,K = list(map(int, input().split()))
a = [[0] * (C+1) for i in range(R+1)]
dp = [[[0] * (C+1) for i in range(R+1)] for j in range(4)]
for i in range(K):
  r,c,v = list(map(int, input().split()))
  a[r-1][c-1] = v
  
for i in range(R):
  for j in range(C):
    for k in range(2,-1,-1):
      dp[k+1][i][j] = max(dp[k+1][i][j], dp[k][i][j] + a[i][j])
    for k in range(4):
      dp[0][i+1][j] = max(dp[0][i+1][j], dp[k][i][j])
      dp[k][i][j+1] = max(dp[k][i][j+1], dp[k][i][j])
ans = 0
for k in range(4):
  ans = max(ans, dp[k][R-1][C-1])
print(ans)

# Optimized solution
R,C,K = list(map(int, input().split()))
a = [[0] * (C+1) for i in range(R+1)]
dp = [[[0] * (C+1) for i in range(R+1)] for j in range(4)]

for i in range(K):
  r,c,v = list(map(int, input().split()))
  r -= 1
  c -= 1
  a[r][c] = v 
  
for i in range(R):
  for j in range(C):
    for k in range(2,-1,-1):
      dp[k+1][i][j] = max(dp[k+1][i][j], dp[k][i][j] + a[i][j])
    for k in range(4):
      dp[k][i][j+1] = max(dp[k][i][j+1], dp[k][i][j])
      dp[0][i+1][j] = max(dp[0][i+1][j], dp[k][i][j])
ans = 0
for k in range(4):
  ans = max(ans, dp[k][R-1][C-1])
  
print(ans)
# Original solution
from copy import deepcopy

def getval():
    r,c,k = list(map(int,input().split()))
    item = [[0 for i in range(c)] for i in range(r)]
    for i in range(k):
        ri,ci,vi = list(map(int,input().split()))
        item[ri-1][ci-1] = vi
    return r,c,k,item

def main(r,c,k,item):
    #DP containing the information of max value given k items picked in i,j
    prev = [[0 for i in range(4)]]
    inititem = item[0][0]
    prev[0] = [0,inititem,inititem,inititem]
    for i in range(1,r):
        initval = prev[i-1][3]
        temp = []
        cur = item[i][0]
        for j in range(4):
            temp.append(initval)
        for j in range(1,4):
            temp[j] += cur
        prev.append(temp)

    for j in range(1,c):
        init = deepcopy(prev[0])
        for i in range(1,4):
            init[i] = prev[0][i]
            if prev[0][i-1]+item[0][j]>init[i]:
                init[i] = prev[0][i-1]+item[0][j]
        curcol = [init]
        for i in range(1,r):
            cur = item[i][j]
            left = curcol[-1][3]
            down = prev[i]
            temp = [left]
            if down[0]>temp[0]:
                temp[0] = down[0]
            for k in range(1,4):
                c = down[k]
                if left+cur>c:
                    c = left+cur 
                if down[k-1]+cur>c:
                    c = down[k-1]+cur
                temp.append(c)
            curcol.append(temp)
        prev = deepcopy(curcol)
            
    print((max(prev[-1])))
    #print(prev)
           
if __name__=="__main__":
    r,c,k,item = getval()
    main(r,c,k,item) 

# Optimized solution
from copy import deepcopy

def getval():
    r,c,k = list(map(int,input().split()))
    item = [[0 for i in range(c)] for i in range(r)]
    for i in range(k):
        ri,ci,vi = list(map(int,input().split()))
        item[ri-1][ci-1] = vi
    return r,c,k,item

def main(r,c,k,item):
    #DP containing the information of max value given k items picked in i,j
    prev = [[0 for i in range(4)]]
    inititem = item[0][0]
    prev[0] = [0,inititem,inititem,inititem]
    for i in range(1,r):
        initval = prev[i-1][3]
        temp = []
        cur = item[i][0]
        for j in range(4):
            temp.append(initval)
        for j in range(1,4):
            temp[j] += cur
        prev.append(temp)

    for j in range(1,c):
        init = deepcopy(prev[0])
        for i in range(1,4):
            init[i] = max(prev[0][i],prev[0][i-1]+item[0][j])
        curcol = [init]
        for i in range(1,r):
            cur = item[i][j]
            left = curcol[-1]
            down = prev[i]
            temp = [max(left[3],down[0])]
            for k in range(1,4):
                temp.append(max(max(left[3],down[k-1])+cur,down[k]))
            curcol.append(temp)
        prev = curcol
            
    print((max(prev[-1])))
           
if __name__=="__main__":
    r,c,k,item = getval()
    main(r,c,k,item)
# Original solution
# pypy
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
from collections import defaultdict

R, C, K = list(map(int, readline().split()))
rcv = list(map(int, read().split()))
rc2v = defaultdict(int)
for rr, cc, vv in zip(rcv[::3], rcv[1::3], rcv[2::3]):
    rc2v[(rr-1, cc-1)] = vv

dp = [[[0]*4 for c in range(C)] for r in range(2)]
dp[0][0][1] = rc2v[(0, 0)]

for c in range(1, C):
  for k in range(1, 4):
    dp[0][c][k] = max(dp[0][c-1][k], dp[0][c-1][k-1]+rc2v[(0, c)])

for r in range(1, R):
  rr = r % 2
  dp[rr][0][0] = max(dp[rr-1][0])
  dp[rr][0][1] = dp[rr][0][0] + rc2v[(r, 0)]
  for c in range(1, C):
    temp_max = max(dp[rr-1][c])
    dp[rr][c][1] = max(dp[rr][c-1][1], max(dp[rr][c-1][0], temp_max)+rc2v[(r, c)])
    for k in range(2, 4):
      dp[rr][c][k] = max(dp[rr][c-1][k], dp[rr][c-1][k-1]+rc2v[(r, c)])
    
if R % 2:
  print((max(dp[0][-1])))
else:
  print((max(dp[-1][-1])))

# Optimized solution
# pypy
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

R, C, K = list(map(int, readline().split()))
rcv = list(map(int, read().split()))
rc2v = {}
for rr, cc, vv in zip(rcv[::3], rcv[1::3], rcv[2::3]):
    rc2v[(rr-1, cc-1)] = vv

dp = [[[0]*4 for c in range(C)] for r in range(2)]
dp[0][0][1] = rc2v[(0, 0)] if (0, 0) in rc2v else 0

for c in range(1, C):
  for k in range(1, 4):
    v = rc2v[(0, c)] if (0, c) in rc2v else 0
    dp[0][c][k] = max(dp[0][c-1][k], dp[0][c-1][k-1]+v)

for r in range(1, R):
  rr = r % 2
  dp[rr][0][0] = max(dp[rr-1][0])
  v = rc2v[(r, 0)] if (r, 0) in rc2v else 0
  dp[rr][0][1] = dp[rr][0][0] + v
  for c in range(1, C):
    v = rc2v[(r, c)] if (r, c) in rc2v else 0
    temp_max = max(dp[rr-1][c])
    dp[rr][c][1] = max(dp[rr][c-1][1], max(dp[rr][c-1][0], temp_max)+v)
    for k in range(2, 4):
      dp[rr][c][k] = max(dp[rr][c-1][k], dp[rr][c-1][k-1]+v)
    
if R % 2:
  print((max(dp[0][-1])))
else:
  print((max(dp[-1][-1])))
# Original solution
# pypy
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

R, C, K = list(map(int, readline().split()))
rcv = list(map(int, read().split()))
rc2v = {}
for rr, cc, vv in zip(rcv[::3], rcv[1::3], rcv[2::3]):
    rc2v[(rr-1, cc-1)] = vv

dp = [[[0]*4 for c in range(C)] for r in range(2)]
dp[0][0][1] = rc2v[(0, 0)] if (0, 0) in rc2v else 0

for c in range(1, C):
  for k in range(1, 4):
    v = rc2v[(0, c)] if (0, c) in rc2v else 0
    dp[0][c][k] = max(dp[0][c-1][k], dp[0][c-1][k-1]+v)

for r in range(1, R):
  rr = r % 2
  dp[rr][0][0] = max(dp[rr-1][0])
  v = rc2v[(r, 0)] if (r, 0) in rc2v else 0
  dp[rr][0][1] = dp[rr][0][0] + v
  for c in range(1, C):
    v = rc2v[(r, c)] if (r, c) in rc2v else 0
    temp_max = max(dp[rr-1][c])
    dp[rr][c][1] = max(dp[rr][c-1][1], max(dp[rr][c-1][0], temp_max)+v)
    for k in range(2, 4):
      dp[rr][c][k] = max(dp[rr][c-1][k], dp[rr][c-1][k-1]+v)
    
if R % 2:
  print((max(dp[0][-1])))
else:
  print((max(dp[-1][-1])))

# Optimized solution
# pypy
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

R, C, K = list(map(int, readline().split()))
rcv = list(map(int, read().split()))
rc2v = {}
for rr, cc, vv in zip(rcv[::3], rcv[1::3], rcv[2::3]):
    rc2v[(rr, cc)] = vv

dp = [[0]*4 for c in range(C+1)]
for r in range(1, R+1):
  for c in range(1, C+1):
    v = rc2v[(r, c)] if (r, c) in rc2v else 0
    dp[c][0] = max(dp[c-1][0], max(dp[c]))
    dp[c][1] = max(dp[c-1][1], dp[c][0] + v)
    for k in range(2, 4):
      dp[c][k] = max(dp[c-1][k], dp[c-1][k-1] + v)

print((max(dp[-1])))
# Original solution
import sys
input=sys.stdin.readline
H,W,K=list(map(int,input().split()))
G=[[0]*W for i in range(H)]

for i in range(K):
    r,c,v=list(map(int,input().split()))
    r,c=r-1,c-1
    G[r][c]=v

dp=[[[-1,-1,-1,-1] for i in range(W)] for i in range(H)]

dp[0][0][0]=0
if G[0][0]!=0:
    dp[0][0][1]=G[0][0]

for i in range(H):
    for j in range(W):
        m=max(dp[i][j])
        if i+1<H:
            dp[i+1][j][1]=max(dp[i+1][j][1],m+G[i+1][j])
            dp[i+1][j][0]=max(dp[i+1][j][0],m)
        if j+1<W:
                dp[i][j+1][0]=0
                dp[i][j+1][1]=max(dp[i][j+1][1],dp[i][j][1],dp[i][j][0]+G[i][j+1])
                dp[i][j+1][2]=max(dp[i][j+1][2],dp[i][j][2],dp[i][j][1]+G[i][j+1])
                dp[i][j+1][3]=max(dp[i][j+1][3],dp[i][j][3],dp[i][j][2]+G[i][j+1])
print((max(dp[H-1][W-1])))

# Optimized solution
import sys
input=sys.stdin.readline
H,W,K=list(map(int,input().split()))
G=[[0]*W for i in range(H)]

for i in range(K):
    r,c,v=list(map(int,input().split()))
    r,c=r-1,c-1
    G[r][c]=v


dp0=[[-1 for i in range(W)] for i in range(H)]
dp1=[[-1 for i in range(W)] for i in range(H)]
dp2=[[-1 for i in range(W)] for i in range(H)]
dp3=[[-1 for i in range(W)] for i in range(H)]

dp0[0][0]=0
if G[0][0]!=0:
    dp1[0][0]=G[0][0]

for i in range(H):
    for j in range(W):
        m=max(dp0[i][j],dp1[i][j],dp2[i][j],dp3[i][j])
        if i+1<H:
            dp1[i+1][j]=max(dp1[i+1][j],m+G[i+1][j])
            dp0[i+1][j]=max(dp0[i+1][j],m)
        if j+1<W:
                dp0[i][j+1]=0
                dp1[i][j+1]=max(dp1[i][j+1],dp1[i][j],dp0[i][j]+G[i][j+1])
                dp2[i][j+1]=max(dp2[i][j+1],dp2[i][j],dp1[i][j]+G[i][j+1])
                dp3[i][j+1]=max(dp3[i][j+1],dp3[i][j],dp2[i][j]+G[i][j+1])
print((max(dp0[H-1][W-1],dp1[H-1][W-1],dp2[H-1][W-1],dp3[H-1][W-1])))
# Original solution
"""
dp[i][j]　=> i行目j列目がゴールの場合の最大値
"""
def main():
    import sys
    input = sys.stdin.readline
    R,C,K = list(map(int,input().split()))
    items = [[0]*(C) for _ in range(R)]

    for _ in range(K):
        r,c,v = list(map(int,input().split()))
        items[r-1][c-1] = v

    dp = [[[0]*4 for _ in range(C)] for _ in range(R)]
    dp[0][0][1] = items[0][0]
    for i in range(R):
        for j in range(C):
            v = items[i][j]
            if i==0 and j == 0:
                continue

            if i!=0:
                #上から入る場合のシミュレート
                dp[i][j][0] = max(dp[i][j][0],max(dp[i-1][j]))
                if v:
                    dp[i][j][1] = max(dp[i][j][1],max(dp[i-1][j])+v)

            if j!=0:
                #左から入る場合のシミュレート
                dp[i][j][0] = max(dp[i][j][0],dp[i][j-1][0])
                if v:
                    #itemが存在する場合の処理
                    for k in range(1,4):
                        dp[i][j][k] = max(dp[i][j][k],dp[i][j-1][k-1]+v,dp[i][j-1][k])
                else:
                    for k in range(1,4):
                        dp[i][j][k] = max(dp[i][j][k],dp[i][j-1][k])
    print((max(dp[-1][-1])))
main()

# Optimized solution
"""
dp[i][j]　=> i行目j列目がゴールの場合の最大値
"""
def main():
    import sys
    input = sys.stdin.readline
    R,C,K = list(map(int,input().split()))
    items = [[0]*(C) for _ in range(R)]

    for _ in range(K):
        r,c,v = list(map(int,input().split()))
        items[r-1][c-1] = v

    dp = [[0]*4 for _ in range(C)]
    dp[0][1] = items[0][0]
    for i in range(R):
        for j in range(C):
            v = items[i][j]
            if i==0 and j == 0:
                continue

            if i!=0:
                #上から入る場合のシミュレート
                dp[j][0] = max(dp[j])
                if v:
                    dp[j][1] = dp[j][0]+v

            if j!=0:
                #左から入る場合のシミュレート
                dp[j][0] = max(dp[j][0],dp[j-1][0])
                if v:
                    #itemが存在する場合の処理
                    for k in range(1,4):
                        dp[j][k] = max(dp[j][k],dp[j-1][k-1]+v,dp[j-1][k])
                else:
                    for k in range(1,4):
                        dp[j][k] = max(dp[j][k],dp[j-1][k])
    print((max(dp[-1])))
main()