CodeEff/ECCO huggingface dataset:
# Original solution
R, C, K=list(map(int, input().split()))
math=[[0]*C for _ in range(R)]
for _ in range(K):
  r, c, v=list(map(int, input().split()))
  math[r-1][c-1]=v
  
dp=[[[0]*4 for __ in range(C)] for _ in range(R)]
if math[0][0]>0:
  dp[0][0][1]=math[0][0]+0
  
for j in range(1, C):
  dp[0][j][0]=dp[0][j-1][0]+0
  dp[0][j][1]=max(dp[0][j-1][1], dp[0][j-1][0]+math[0][j])
  dp[0][j][2]=max(dp[0][j-1][2], dp[0][j-1][1]+math[0][j])
  dp[0][j][3]=max(dp[0][j-1][3], dp[0][j-1][2]+math[0][j])
    
for i in range(1, R):
  dp[i][0][0]=max(dp[i-1][0])
  dp[i][0][1]=dp[i][0][0]+math[i][0]
  for j in range(1, C):
    dp[i][j][0]=max(dp[i][j-1][0], max(dp[i-1][j]))
    dp[i][j][1]=max(dp[i][j-1][1], dp[i][j-1][0]+math[i][j], max(dp[i-1][j])+math[i][j])
    dp[i][j][2]=max(dp[i][j-1][2], dp[i][j-1][1]+math[i][j])
    dp[i][j][3]=max(dp[i][j-1][3], dp[i][j-1][2]+math[i][j])
    
print((max(dp[-1][-1])))

# Optimized solution
R, C, K=list(map(int, input().split()))
math=[[0]*C for _ in range(R)]
for _ in range(K):
  r, c, v=list(map(int, input().split()))
  math[r-1][c-1]=v
  
dp=[[[0]*C for __ in range(R)] for _ in range(4)]
if math[0][0]>0:
  dp[1][0][0]=math[0][0]+0
  
for j in range(1, C):
  dp[0][0][j]=dp[0][0][j-1]+0
  dp[1][0][j]=max(dp[1][0][j-1], dp[0][0][j-1]+math[0][j])
  dp[2][0][j]=max(dp[2][0][j-1], dp[1][0][j-1]+math[0][j])
  dp[3][0][j]=max(dp[3][0][j-1], dp[2][0][j-1]+math[0][j])
    
for i in range(1, R):
  dp[0][i][0]=max(dp[0][i-1][0], dp[1][i-1][0], dp[2][i-1][0], dp[3][i-1][0])
  dp[1][i][0]=dp[0][i][0]+math[i][0]
  for j in range(1, C):
    dp[0][i][j]=max(dp[0][i][j-1], max(dp[0][i-1][j], dp[1][i-1][j], dp[2][i-1][j], dp[3][i-1][j]))
    dp[1][i][j]=max(dp[1][i][j-1], dp[0][i][j-1]+math[i][j], max(dp[0][i-1][j], dp[1][i-1][j], dp[2][i-1][j], dp[3][i-1][j])+math[i][j])
    dp[2][i][j]=max(dp[2][i][j-1], dp[1][i][j-1]+math[i][j])
    dp[3][i][j]=max(dp[3][i][j-1], dp[2][i][j-1]+math[i][j])
    
print((max(dp[0][-1][-1], dp[1][-1][-1], dp[2][-1][-1], dp[3][-1][-1])))
# Original solution
R, C,K = list(map(int, input().split()))
dp = [[[0]*(C+1) for k in range(R+1)] for _ in range(4)]
# dp[r][c][j] :=r index c columns already j cnt
dp[0][0][0] = 0
D = [[0 for i in range(C+1)] for j in range(R+1)]
import random
for i in range(K):
    r, c, v = list(map(int,input().split()))
    D[r][c] = v

for i in range(R+1):
    for j in range(C+1):
        if D[i][j] > 0:
            v = D[i][j]
            M = max(dp[k][i-1][j] for k in range(4))
            dp[0][i][j] = max(dp[0][i][j-1], M)
            dp[1][i][j] = max(dp[0][i][j-1]+v, dp[1][i][j-1], M+v)
            dp[2][i][j] = max(dp[1][i][j-1]+v, dp[2][i][j-1])
            dp[3][i][j] = max(dp[2][i][j-1]+v, dp[3][i][j-1])

        else:
            M = max(dp[k][i-1][j] for k in range(4))
            dp[0][i][j] = max(dp[0][i][j-1], M)
            dp[1][i][j] = dp[1][i][j-1]
            dp[2][i][j] = dp[2][i][j-1]
            dp[3][i][j] = dp[3][i][j-1]

ans = 0
for i in range(4):
    ans = max(ans, dp[i][-1][-1])
print(ans)


# Optimized solution
## 一時間もTLEのために時間を無駄にした　学びもないつまんない問題...

R, C, K = list(map(int, input().split()))
dp = [[[0]*(C+1) for _ in range(R+1)]for __ in range(4)]
# dp[r][c][j] :=r index c columns already j cnt
dp[0][0][0] = 0
D = [[0 for i in range(C+1)] for j in range(R+1)]

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

for i in range(R+1):
    for j in range(C+1):
        if D[i][j] > 0:
            v = D[i][j]
            M = max(dp[k][i-1][j] for k in range(4))
            dp[0][i][j] = max(dp[0][i][j-1], M)
            dp[1][i][j] = max(dp[0][i][j-1]+v, dp[1][i][j-1], M+v)
            dp[2][i][j] = max(dp[1][i][j-1]+v, dp[2][i][j-1])
            dp[3][i][j] = max(dp[2][i][j-1]+v, dp[3][i][j-1])

        else:
            M = max(dp[k][i-1][j] for k in range(4))
            dp[0][i][j] = max(dp[0][i][j-1], M)
            dp[1][i][j] = dp[1][i][j-1]
            dp[2][i][j] = dp[2][i][j-1]
            dp[3][i][j] = dp[3][i][j-1]

ans = 0
for i in range(4):
    ans = max(ans, dp[i][-1][-1])
print(ans)
# Original solution
def main():

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

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

    for i in range(R):
        for j in range(C):
            v = max(dp[i][j+1])
            u = 0
            if (i, j) in a: u = a[(i, j)]
            dp[i+1][j+1][0] = max(dp[i+1][j+1][0], v)
            dp[i+1][j+1][1] = max(dp[i+1][j+1][1], dp[i+1][j][1], dp[i+1][j][0] + u,  v + u)
            dp[i+1][j+1][2] = max(dp[i+1][j+1][2], dp[i+1][j][2], dp[i+1][j][1] + u )
            dp[i+1][j+1][3] = max(dp[i+1][j+1][3], dp[i+1][j][3], dp[i+1][j][2] + u )

    return max(dp[R][C])

if __name__ == '__main__':
    print((main()))


# Optimized solution
def main():

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

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

    for i in range(R):
        for j in range(C):
            v = max(dp[0][j+1])
            u = 0
            if (i, j) in a: u = a[(i, j)]
            dp[1][j+1][0] = max(dp[1][j+1][0], v)
            dp[1][j+1][1] = max(dp[1][j+1][1], dp[1][j][1], dp[1][j][0] + u,  v + u)
            dp[1][j+1][2] = max(dp[1][j+1][2], dp[1][j][2], dp[1][j][1] + u )
            dp[1][j+1][3] = max(dp[1][j+1][3], dp[1][j][3], dp[1][j][2] + u )
        dp[1], dp[0] = dp[0], dp[1]

    return max(dp[0][C])

if __name__ == '__main__':
    print((main()))
# Original solution
import sys
import copy
from collections import deque

sys.setrecursionlimit(10**6)
input = sys.stdin.readline
#read = sys.stdin.buffer.read

def main():
    global field
    R, C, K = list(map(int, input().split()))
    field = []
    for _ in range(R):
        tmp = [0] * C
        field.append(tmp)
    DP0 = copy.deepcopy(field)
    DP1 = copy.deepcopy(field)
    DP2 = copy.deepcopy(field)
    DP3 = copy.deepcopy(field)

    for _ in range(K):
        r, c, k = list(map(int, input().split()))
        field[r-1][c-1] = k
    
    i = 0
    DP1[0][0] = field[0][0]
    for j in range(1, C):
        DP3[i][j] = max(DP2[i][j-1] + field[i][j], DP3[i][j-1])
        DP2[i][j] = max(DP1[i][j-1] + field[i][j], DP2[i][j-1])
        DP1[i][j] = max(DP0[i][j-1] + field[i][j], DP1[i][j-1])
        DP0[i][j] = DP0[i][j-1]

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

    ans = max(DP3[R-1][C-1], DP2[R-1][C-1], DP1[R-1][C-1], DP0[R-1][C-1])
    print(ans)


if __name__ == "__main__":
    main()


# Optimized solution
import sys
import copy
from collections import deque

sys.setrecursionlimit(10**6)
input = sys.stdin.readline
#read = sys.stdin.buffer.read

def main():
    global field
    R, C, K = list(map(int, input().split()))
    field = []
    for _ in range(R):
        tmp = [0] * C
        field.append(tmp)
    DP1 = copy.deepcopy(field)
    DP2 = copy.deepcopy(field)
    DP3 = copy.deepcopy(field)

    for _ in range(K):
        r, c, k = list(map(int, input().split()))
        field[r-1][c-1] = k
    
    i = 0
    DP1[0][0] = field[0][0]
    for j in range(1, C):
        DP3[i][j] = max(DP2[i][j-1] + field[i][j], DP3[i][j-1])
        DP2[i][j] = max(DP1[i][j-1] + field[i][j], DP2[i][j-1])
        DP1[i][j] = max(field[i][j], DP1[i][j-1])

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

    ans = max(DP3[R-1][C-1], DP2[R-1][C-1], DP1[R-1][C-1])
    print(ans)


if __name__ == "__main__":
    main()
# Original solution
f=lambda:list(map(int,input().split()))
R,C,K=f()
g=[[0]*(C+1) for _ in range(R+1)]
for _ in range(K):
  r,c,v=f()
  g[r][c]=v
dp=[[[0]*4 for _ in range(C+2)] for _ in range(R+2)]
for i in range(1,R+1):
  for j in range(1,C+1):
    for k in range(3,-1,-1):
      if k: dp[i][j][k]=max(dp[i][j][k],dp[i][j][k-1]+g[i][j])
      dp[i+1][j][0]=max(dp[i+1][j][0],dp[i][j][k])
      dp[i][j+1][k]=max(dp[i][j+1][k],dp[i][j][k])
print((max(dp[R][C][k] for k in range(4))))

# Optimized solution
f=lambda:list(map(int,input().split()))
R,C,K=f()
g=[[0]*(R+1) for _ in range(C+1)]
for _ in range(K):
  r,c,v=f()
  g[c][r]=v
dp=[[0]*4 for _ in range(R+1)]
for i in range(1,C+1):
  for j in range(1,R+1):
    t=g[i][j]
    if t:
      for k in range(3,0,-1):
        dp[j][k]=max(dp[j][k],dp[j][k-1]+t)
      dp[j][1]=max(dp[j][k],max(dp[j-1])+t)
    dp[j][0]=max(dp[j][0],max(dp[j-1]))
print((max(dp[R])))
# Original solution
f=lambda:list(map(int,input().split()))
R,C,K=f()
g=[[0]*(C+1) for _ in range(R+1)]
for _ in range(K):
  r,c,v=f()
  g[r][c]=v
dp=[[[0]*(C+2) for _ in range(R+2)] for _ in range(4)]
for i in range(1,R+1):
  for j in range(1,C+1):
    for k in range(3,-1,-1):
      if k: dp[k][i][j]=max(dp[k][i][j],dp[k-1][i][j]+g[i][j])
      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])
print((max(dp[i][R][C] for i in range(4))))

# Optimized solution
f=lambda:list(map(int,input().split()))
R,C,K=f()
g=[[0]*(C+1) for _ in range(R+1)]
for _ in range(K):
  r,c,v=f()
  g[r][c]=v
dp=[[[0]*(C+2) for _ in range(R+2)] for _ in range(4)]
for i in range(1,R+1):
  for j in range(1,C+1):
    for k in range(3,-1,-1):
      if k: dp[k][i][j]=max(dp[k][i][j],dp[k-1][i][j]+g[i][j])
      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])
print((max(dp[k][R][C] for k in range(4))))
# Original solution
import sys
input = sys.stdin.readline

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

items = dict()

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

dp = [0] * 4 * R * C

if (0,0) in items:
    dp[1] = items[(0,0)]

def ind(i,j,k):
    return 4 * C * i + 4 * j + k

for row in range(R):
    for col in range(C):
        for pick in range(4):
            curr = dp[ind(row,col,pick)]
            #Go Right
            if col + 1 < C:
                dp[ind(row,col+1,pick)] = max(curr, dp[ind(row,col+1,pick)])
                if (row, col+1) in items and pick < 3:
                    dp[ind(row,col+1,pick+1)] = max(curr + items[(row,col+1)], dp[ind(row,col+1,pick+1)])
            #Go Down
            if row + 1 < R:
                dp[ind(row+1,col,0)] = max(curr, dp[ind(row+1,col,0)])
                if (row + 1, col) in items:
                    dp[ind(row+1,col,1)] = max(curr + items[(row+1,col)], dp[ind(row+1,col,1)])
                    

print((max(dp)))
            


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

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

items = [0] * R * C

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

dp = [0] * 4 * R * C

dp[1] = items[0]

def ind(i,j,k):
    return 4 * C * i + 4 * j + k

for row in range(R):
    for col in range(C):
        for pick in range(4):
            curr = dp[ind(row,col,pick)]
            #Go Right
            if col + 1 < C:
                dp[ind(row,col+1,pick)] = max(curr, dp[ind(row,col+1,pick)])
                if pick < 3:
                    dp[ind(row,col+1,pick+1)] = max(curr + items[C * row + col+1], dp[ind(row,col+1,pick+1)])
            #Go Down
            if row + 1 < R:
                dp[ind(row+1,col,0)] = max(curr, dp[ind(row+1,col,0)])
                dp[ind(row+1,col,1)] = max(curr + items[C * (row+1) + col], dp[ind(row+1,col,1)])
                    

print((max(dp)))
# Original solution
R,C,K=list(map(int,input().split()))
l=[[0] * C for i in range(R)]
dp=[[[0] * 4 for i in range(C)] for j in range(R)]
for i in range(K):
  a,b,c=list(map(int,input().split()))
  a-=1
  b-=1
  l[a][b]=c
dp[0][0][1]=l[0][0]
for x in range(1,R+C-1):
  for y in range(R):
    i=y
    j=x-y
    if j<0 or C<=j:
      continue
    for k in range(4):
      A=0
      if 0<j:
        A=max(A,dp[i][j-1][k])
        if 0<k:
          A=max(A,dp[i][j-1][k-1]+l[i][j])
      if 0<i and k<2:
        for q in range(4):
          A=max(A,dp[i-1][j][q]+k*l[i][j])
      dp[i][j][k]=A
X=dp[R-1][C-1][3]
for k in range(3):
  X=max(X,dp[R-1][C-1][k])
print(X)
    

# Optimized solution
R,C,K=list(map(int,input().split()))
l=[[0] * C for i in range(R)]
for i in range(K):
  a,b,c=list(map(int,input().split()))
  a-=1
  b-=1
  l[a][b]=c
dp=[0]*C
for i in range(R):
  ndp=[0]*C
  kdp=[0]*4
  kdp[0]=dp[0]
  kdp[1]=l[i][0]+dp[0]
  ndp[0]=kdp[1]
  for j in range(1,C):
    kdp[0]=max(kdp[0],dp[j])
    for k in range(2,-1,-1):
      kdp[k+1]=max(kdp[k+1],kdp[k]+l[i][j])
    ndp[j]=max(kdp)
  dp=ndp
print((dp[C-1]))
# Original solution
R,C,K=list(map(int,input().split()))
l=[[0] * C for i in range(R)]
for i in range(K):
  a,b,c=list(map(int,input().split()))
  a-=1
  b-=1
  l[a][b]=c
dp=[0]*C
for i in range(R):
  ndp=[0]*C
  kdp=[0]*4
  kdp[0]=dp[0]
  kdp[1]=l[i][0]+dp[0]
  ndp[0]=kdp[1]
  for j in range(1,C):
    kdp[0]=max(kdp[0],dp[j])
    for k in range(2,-1,-1):
      kdp[k+1]=max(kdp[k+1],kdp[k]+l[i][j])
    ndp[j]=max(kdp)
  dp=ndp
print((dp[C-1]))

# Optimized solution
R,C,K=list(map(int,input().split()))
l=[[0] * C for i in range(R)]
for i in range(K):
  a,b,c=list(map(int,input().split()))
  a-=1
  b-=1
  l[a][b]=c
dp=[0]*C
for i in range(R):
  ndp=[0]*C
  kdp=[0]*4
  for j in range(0,C):
    kdp[0]=max(kdp[0],dp[j])
    for k in range(2,-1,-1):
      kdp[k+1]=max(kdp[k+1],kdp[k]+l[i][j])
    ndp[j]=max(kdp)
  dp=ndp
print((dp[C-1]))
# Original solution
R,C,K=list(map(int,input().split()))
l=[[0] * C for i in range(R)]
for i in range(K):
  a,b,c=list(map(int,input().split()))
  a-=1
  b-=1
  l[a][b]=c
dp=[0]*C
for i in range(R):
  ndp=[0]*C
  kdp=[0]*4
  for j in range(0,C):
    kdp[0]=max(kdp[0],dp[j])
    for k in range(2,-1,-1):
      kdp[k+1]=max(kdp[k+1],kdp[k]+l[i][j])
    ndp[j]=max(kdp)
  dp=ndp
print((dp[C-1]))


# Optimized solution
R,C,K=list(map(int,input().split()))
l=[[0] * C for i in range(R)]
for i in range(K):
  a,b,c=list(map(int,input().split()))
  a-=1
  b-=1
  l[a][b]=c
dp=[[0] * C for i in range(R)]
for i in range(R):
  kdp=[0]*4
  for j in range(C):
    if i>0:
      kdp[0]=max(kdp[0],dp[i-1][j])
    for k in range(2,-1,-1):
      kdp[k+1]=max(kdp[k+1],kdp[k]+l[i][j])
      dp[i][j]=max(dp[i][j],kdp[k+1])
print((dp[R-1][C-1]))
# Original solution
#!/usr/bin/env python3

import collections
import sys
input=sys.stdin.readline

r,c,k=list(map(int,input().split()))
items=collections.defaultdict(int)
for _ in range(k):
    tr,tc,tv=list(map(int,input().split()))
    items[(tr,tc)]=tv
dp=[[[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):
        tv=items[(i,j)]
        left_max=max(dp[i-1][j])
        #左から来るときは取った個数をリセットする
        dp[i][j][0]=max(dp[i][j-1][0],left_max)
        dp[i][j][1]=max(dp[i][j-1][1],dp[i][j-1][0]+tv,left_max+tv)        
        dp[i][j][2]=max(dp[i][j-1][2],dp[i][j-1][1]+tv)
        dp[i][j][3]=max(dp[i][j-1][3],dp[i][j-1][2]+tv)
print((max(dp[r][c])))

# Optimized solution
#!/usr/bin/env python3

import sys
input=sys.stdin.readline

r,c,k=list(map(int,input().split()))
items=[0]*(r*c)
for _ in range(k):
    tr,tc,tv=list(map(int,input().split()))
    items[c*(tr-1)+tc-1]=tv
dp=[0]*(4*r*c)
for i in range(1,r+1):
    for j in range(1,c+1):
        tv=items[c*(i-1)+j-1]
        change_pos=4*(c*(i-1)+j-1)
        left_pos=4*(c*(i-2)+j-1)
        up_pos=4*(c*(i-1)+j-2)
        if i!=1:
          left_max=max(dp[left_pos],dp[left_pos+1],dp[left_pos+2],dp[left_pos+3])
        else:
          left_max=0
        if j!=1:
          dp[change_pos]=max(dp[up_pos],left_max)
          dp[change_pos+1]=max(dp[up_pos+1],dp[up_pos]+tv,left_max+tv)        
          dp[change_pos+2]=max(dp[up_pos+2],dp[up_pos+1]+tv)
          dp[change_pos+3]=max(dp[up_pos+3],dp[up_pos+2]+tv)
        else:
          dp[change_pos]=left_max
          dp[change_pos+1]=left_max+tv
print((max(dp[-1],dp[-2],dp[-3],dp[-4])))
# Original solution
import sys
input=sys.stdin.readline
def main():
    r,c,k=list(map(int,input().split()))
    v=dict()
    for _ in range(k):
        ri,ci,a=list(map(int,input().split()))
        ri-=1
        ci-=1
        v[(ri,ci)]=a
    dp=[[[0]*4 for _ in range(c)] for i in range(r)]
    #print(dp)
    if (0,0) in v:
        if v[(0,0)]>0:
            dp[0][0][1]=v[(0,0)]
    for i in range(r):
        for j in range(c):
            if i>0:
                if (i,j) in v:
                    if v[(i,j)]>0:
                        for k in range(min(3,j+1)+1):
                            dp[i][j][1]=max(dp[i][j][1],dp[i-1][j][k]+v[(i,j)])
                for k in range(4):
                    dp[i][j][k]=max(dp[i][j][k],dp[i-1][j][k])
            if j>0:
                if (i,j) in v:
                    if v[(i,j)]>0:
                        for k in range(min(3,j+1)+1):
                            if k>0:
                                dp[i][j][k]=max(dp[i][j][k],dp[i][j-1][k-1]+v[(i,j)])
                for k in range(4):
                    dp[i][j][k]=max(dp[i][j][k],dp[i][j-1][k])
    #print(dp)
    print((max(dp[r-1][c-1])))
if __name__=="__main__":
    main()

# Optimized solution
import sys
input=sys.stdin.readline
def main():
    r,c,k=map(int,input().split())
    v=[[0]*c for _ in range(r)]
    for _ in range(k):
        ri,ci,a=map(int,input().split())
        ri-=1
        ci-=1
        v[ri][ci]=a
    dp=[[[0]*c for _ in range(r)] for i in range(4)]
    #print(dp)
    if v[0][0]>0:
        dp[1][0][0]=v[0][0]
    for i in range(r):
        for j in range(c):
            for k in range(4):
                if i>0:
                    dp[1][i][j]=max(dp[1][i][j],dp[k][i-1][j]+v[i][j])
                    dp[0][i][j]=max(dp[0][i][j],dp[k][i-1][j])
                if j>0:
                    if k>0:
                        dp[k][i][j]=max(dp[k][i][j],dp[k-1][i][j-1]+v[i][j])
                    dp[k][i][j]=max(dp[k][i][j],dp[k][i][j-1])
    #print(dp)
    ans=0
    for i in range(4):
        ans=max(dp[i][r-1][c-1],ans)
    return print(ans)
if __name__=="__main__":
    main()
# Original solution
def main(R,C,K,V):
    dp = [[[0,0,0,0] for _ in range(C)] for _ in range(R)]
    dp[0][0][1] = V[0][0]
    for i in range(R):
        for j in range(C):
            for n in range(4):
                if n!=0:
                    if i != 0 and n==1:
                        dp[i][j][n] = max(dp[i-1][j][0],dp[i-1][j][1],dp[i-1][j][2],dp[i-1][j][3])+V[i][j]
                    if j != 0:
                        dp[i][j][n] = max(dp[i][j][n],dp[i][j-1][n],dp[i][j-1][n-1]+V[i][j])
                if n==0:
                    if i != 0:
                        dp[i][j][n] = max(dp[i-1][j][0],dp[i-1][j][1],dp[i-1][j][2],dp[i-1][j][3])

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

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

# Optimized solution
def main(R,C,K,V):
    dp = [0]*(4*R*C)
    dp[1+4*0+4*C*0] = V[0][0]
    for k in range(4*R*C):
        n = k%4
        j = k//4%C
        i = k//(4*C)
        if n!=0:
            if i != 0 and n==1:
                dp[k] = max(dp[k-4*C-n:k-4*C-n+4])+V[i][j]
            if j != 0:
                dp[k] = max(dp[k],dp[k-4],dp[k-5]+V[i][j])
        if n==0:
            if i != 0:
                dp[k] = max(dp[k-4*C-n:k-4*C-n+4])

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

if __name__ == '__main__':
    R,C,K = list(map(int,input().split()))
    C += 1
    rcv = [list(map(int,input().split())) for _ in range(K)]
    V = [[0]*C for _ in range(R)]
    for i in range(K):
        r,c,v = rcv[i]
        r -= 1
        c -= 1
        V[r][c] = v
    main(R,C,K,V)
# Original solution
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

r, c, k = LI()
maze = [[0] * c for _ in range(r)]
for _ in range(k):
    R, C, V = LI()
    maze[R-1][C-1] = V

dp1 = [[0] * (c+1) for _ in range(r+1)]
dp2 = [[0] * (c+1) for _ in range(r+1)]
dp3 = [[0] * (c+1) for _ in range(r+1)]

for i in range(1, r+1):
    for j in range(1, c+1):
        dp1[i][j] = max(dp1[i][j-1], dp1[i-1][j] + maze[i-1][j-1], maze[i-1][j-1], dp2[i-1][j] + maze[i-1][j-1], dp3[i-1][j] + maze[i-1][j-1])
        dp2[i][j] = max(dp2[i][j-1], dp2[i-1][j], dp1[i][j-1] + maze[i-1][j-1])
        dp3[i][j] = max(dp3[i][j-1], dp3[i-1][j], dp2[i][j-1] + maze[i-1][j-1])
ans = max(dp1[-1][-1], dp2[-1][-1], dp3[-1][-1])
print(ans)

# Optimized solution
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

r, c, k = LI()
maze = [[0] * (c+1) for _ in range(r+1)]
for _ in range(k):
    R, C, V = LI()
    maze[R][C] = V

dp1 = [[0] * (c+1) for _ in range(r+1)]
dp2 = [[0] * (c+1) for _ in range(r+1)]
dp3 = [[0] * (c+1) for _ in range(r+1)]

for i in range(1, r+1):
    for j in range(1, c+1):
        dp1[i][j] = max(dp1[i][j-1], dp1[i-1][j] + maze[i][j], dp2[i-1][j] + maze[i][j], dp3[i-1][j] + maze[i][j])
        dp2[i][j] = max(dp2[i][j-1], dp1[i][j-1] + maze[i][j])
        dp3[i][j] = max(dp3[i][j-1], dp2[i][j-1] + maze[i][j])
ans = max(dp1[-1][-1], dp2[-1][-1], dp3[-1][-1])
print(ans)
# Original solution
#!/usr/bin/env python3
r, c, k = list(map(int, input().split()))
items = [[0] * (c+1) for _ in range(r+1)]
for _ in range(k):
    R, C, V = list(map(int, input().split()))
    items[R][C] = V

dp0 = [[0] * (c+1) for _ in range(r+1)]
dp1 = [[0] * (c+1) for _ in range(r+1)]
dp2 = [[0] * (c+1) for _ in range(r+1)]
dp3 = [[0] * (c+1) for _ in range(r+1)]

for i in range(1, r+1):
    for j in range(1, c+1):
        dp0[i][j] = max(dp0[i][j-1], dp0[i-1][j], dp1[i-1][j], dp2[i-1][j], dp3[i-1][j])
        dp1[i][j] = max(dp1[i][j-1], dp0[i-1][j] + items[i][j], dp1[i-1][j] + items[i][j], dp2[i-1][j] + items[i][j], dp3[i-1][j] + items[i][j], dp0[i][j-1] + items[i][j])
        dp2[i][j] = max(dp2[i][j-1], dp1[i][j-1] + items[i][j])
        dp3[i][j] = max(dp3[i][j-1], dp2[i][j-1] + items[i][j])

ans = max(dp0[r][c], dp1[r][c], dp2[r][c], dp3[r][c])
print(ans)

# Optimized solution
#!/usr/bin/env python3
r, c, k = list(map(int, input().split()))
items = [[0] * (c+1) for _ in range(r+1)]
for _ in range(k):
    R, C, V = list(map(int, input().split()))
    items[R][C] = V

dp1 = [[0] * (c+1) for _ in range(r+1)]
dp2 = [[0] * (c+1) for _ in range(r+1)]
dp3 = [[0] * (c+1) for _ in range(r+1)]

for i in range(1, r+1):
    for j in range(1, c+1):
        dp1[i][j] = max(dp1[i][j-1], dp1[i-1][j] + items[i][j], dp2[i-1][j] + items[i][j], dp3[i-1][j] + items[i][j])
        dp2[i][j] = max(dp2[i][j-1], dp1[i][j-1] + items[i][j])
        dp3[i][j] = max(dp3[i][j-1], dp2[i][j-1] + items[i][j])

ans = max(dp1[r][c], dp2[r][c], dp3[r][c])
print(ans)