CodeEff/ECCO huggingface dataset:
# Original solution
import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(eval(input()))
rl = lambda: list(map(int, input().split()))
mod = 1000000007
sys.setrecursionlimit(1000000)

R, C, K = rl()
I = [[0]*(C+2) for _ in range(R+2)]
for i in range(K):
	r, c, v = rl()
	I[r][c] = v

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

for i in range(R+1):
	for j in range(C+1):
		d = dp[i][j]
		for ni, nj in [[i+1, j], [i, j+1]]:
			nd = dp[ni][nj]
			v = I[ni][nj]
			for m in range(4):
				if i == ni:
					nd[m] = max(nd[m], d[m])
					if m < 3:
						nd[m+1] = max(nd[m+1], d[m]+v)
				else:
					nd[0] = max(nd[0], d[m])
					nd[1] = max(nd[1], d[m] + v)
ans = 0
for m in range(4):
	ans = max(ans, dp[R][C][m])
print(ans)


# Optimized solution
import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(eval(input()))
rl = lambda: list(map(int, input().split()))
mod = 1000000007
sys.setrecursionlimit(1000000)
 
R, C, K = rl()
I = [[0]*(C+2) for _ in range(R+2)]
for i in range(K):
	r, c, v = rl()
	I[r][c] = 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 m in range(4):
			ni, nj = i, j+1
			dp[m][ni][nj] = max(dp[m][ni][nj], dp[m][i][j])
			if m < 3:
				dp[m+1][ni][nj] = max(dp[m+1][ni][nj], dp[m][i][j]+I[ni][nj])
			ni, nj = i+1, j
			dp[0][ni][nj] = max(dp[0][ni][nj], dp[m][i][j])
			dp[1][ni][nj] = max(dp[1][ni][nj], dp[m][i][j]+I[ni][nj])
ans = 0
for m in range(4):
	ans = max(ans, dp[m][R][C])
print(ans)
# Original solution
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict
R,C,K=list(map(int, sys.stdin.readline().split()))

value=defaultdict(lambda: 0)
value=[ [0 for _ in range(C+1)] for __ in range(R+1) ]
for _ in range(K):
    r,c,v=list(map(int, sys.stdin.readline().split()))
    value[r][c]=v

dp0=[0]*(C+1)
dp1=[0]*(C+1)
dp2=[0]*(C+1)
dp3=[0]*(C+1)

for r in range(1,R+1):
    for c in range(1,C+1):
        #今のマスにアイテムがある場合
        if 0<value[r][c]:
            dp3[c]=max( dp3[c-1], dp2[c-1]+value[r][c] )
            dp2[c]=max( dp2[c-1], dp1[c-1]+value[r][c] )
            dp1[c]=max( dp1[c-1], dp0[c-1]+value[r][c], dp0[c]+value[r][c] )
            dp0[c]=max( dp0[c-1], dp0[c] )
        #今のマスにアイテムがない場合
        else:
            #dp0[c]=max( dp0[c-1], dp0[c] )
            #dp1[c]=max( dp1[c-1], dp1[c] )
            #dp2[c]=max( dp2[c-1], dp2[c] )
            #dp3[c]=max( dp3[c-1], dp3[c] )
            dp0[c]=dp0[c]
            dp1[c]=dp1[c-1]
            dp2[c]=dp2[c-1]
            dp3[c]=dp3[c-1]

    #上の行にアイテムをコピー
    for c in range(1,C+1):
        dp0[c]=max( dp0[c], dp1[c], dp2[c], dp3[c] )
    dp1=[0]*(C+1)
    dp2=[0]*(C+1)
    dp3=[0]*(C+1)

print(dp0[C])


# Optimized solution
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict
R,C,K=list(map(int, sys.stdin.readline().split()))

value=defaultdict(lambda: 0)
value=[ [0 for _ in range(C+1)] for __ in range(R+1) ]
for _ in range(K):
    r,c,v=list(map(int, sys.stdin.readline().split()))
    value[r][c]=v

dp0=[0]*(C+1)
dp1=[0]*(C+1)
dp2=[0]*(C+1)
dp3=[0]*(C+1)

for r in range(1,R+1):
    for c in range(1,C+1):
        #今のマスにアイテムがある場合
        if 0<value[r][c]:
            dp3[c]=max( dp3[c-1], dp2[c-1]+value[r][c] )
            dp2[c]=max( dp2[c-1], dp1[c-1]+value[r][c] )
            #dp1[c]=max( dp1[c-1], dp0[c-1]+value[r][c], dp0[c]+value[r][c] )
            dp1[c]=max( dp1[c-1], dp0[c]+value[r][c] )
            #dp0[c]=max( dp0[c-1], dp0[c] )
            dp0[c]=dp0[c]
        #今のマスにアイテムがない場合
        else:
            #dp0[c]=max( dp0[c-1], dp0[c] )
            #dp1[c]=max( dp1[c-1], dp1[c] )
            #dp2[c]=max( dp2[c-1], dp2[c] )
            #dp3[c]=max( dp3[c-1], dp3[c] )
            dp0[c]=dp0[c]
            dp1[c]=dp1[c-1]
            dp2[c]=dp2[c-1]
            dp3[c]=dp3[c-1]

    #上の行にアイテムをコピー
    for c in range(1,C+1):
        dp0[c]=max( dp0[c], dp1[c], dp2[c], dp3[c] )
    dp1=[0]*(C+1)
    dp2=[0]*(C+1)
    dp3=[0]*(C+1)

print(dp0[C])
# Original 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]*4 for _ in range(W+1)]

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

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


# Optimized solution
R, C, K = list(map(int, input().split()))
# = int(input())
p = []
for k in range(K):
  p.append(list(map(int, input().split())))

maps = [[0 for _ in range(C)] for _ in range(R)]
for k in range(K):
  maps[p[k][0]-1][p[k][1]-1] += p[k][2]

point = [[[0, 0, 0] for _ in range(C)] for _ in range(R)]

point[0][0][0] = maps[0][0]

for r in range(R):
  for c in range(C):
    a, b, d = point[r][c][0], point[r][c][1], point[r][c][2]  
    if c < C - 1:
      x = maps[r][c+1]
      y = point[r][c+1]
      y[0] = max(y[0], x, a)
      y[1] = max(y[1], a + x, b)
      y[2] = max(y[2], b + x, d)
      point[r][c+1] = y
    if r < R - 1:
      point[r+1][c][0] = max(point[r+1][c][0], maps[r+1][c] + max(a, b, d))     


print((max(point[-1][-1][0:3])))
# Original solution
R, C, K = list(map(int, input().split()))
# = int(input())
p = []
for k in range(K):
  p.append(list(map(int, input().split())))

maps = [[0 for _ in range(C)] for _ in range(R)]
for k in range(K):
  maps[p[k][0]-1][p[k][1]-1] += p[k][2]

point = [[[0, 0, 0] for _ in range(C)] for _ in range(R)]

point[0][0][0] = maps[0][0]

for r in range(R):
  for c in range(C):
    a, b, d = point[r][c][0], point[r][c][1], point[r][c][2]  
    if c < C - 1:
      x = maps[r][c+1]
      y = point[r][c+1]
      y[0] = max(y[0], x, a)
      y[1] = max(y[1], a + x, b)
      y[2] = max(y[2], b + x, d)
      point[r][c+1] = y
    if r < R - 1:
      point[r+1][c][0] = max(point[r+1][c][0], maps[r+1][c] + max(a, b, d))     


print((max(point[-1][-1][0:3])))

# Optimized solution
R, C, K = list(map(int, input().split()))
# = int(input())
p = []
for k in range(K):
  p.append(list(map(int, input().split())))

maps = [[0 for _ in range(C)] for _ in range(R)]
for k in range(K):
  maps[p[k][0]-1][p[k][1]-1] += p[k][2]

point1 = [[0 for _ in range(C)] for _ in range(R)]
point2 = [[0 for _ in range(C)] for _ in range(R)]
point3 = [[0 for _ in range(C)] for _ in range(R)]

point1[0][0] = maps[0][0]

for r in range(R):
  for c in range(C):
    a, b, d = point1[r][c], point2[r][c], point3[r][c]  
    if c < C - 1:
      x = maps[r][c+1]
      point1[r][c+1] = max(point1[r][c+1], x, a)
      point2[r][c+1] = max(point2[r][c+1], a + x, b)
      point3[r][c+1] = max(point3[r][c+1], b + x, d)
    if r < R - 1:
      point1[r+1][c] = maps[r+1][c] + max(a, b, d)


print((max(point1[-1][-1], point2[-1][-1], point3[-1][-1])))
# Original solution
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,m,k = inpl()
value = [[0 for _ in range(m)] for i in range(n)]
for _ in range(k):
    a,b,c = inpl()
    value[a-1][b-1] = c
dp = [[[0 for _ in range(4)] for i in range(m+5)] for j in range(n+5)]
for i in range(n):
    for j in range(m):
        for k in range(3)[::-1]:
            dp[i][j][k+1] = max(dp[i][j][k+1], dp[i][j][k] + value[i][j])
        for k in range(4):
            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[n-1][m-1])))

# Optimized solution
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,m,k = inpl()
value = [[0 for _ in range(m)] for i in range(n)]
for _ in range(k):
    a,b,c = inpl()
    value[a-1][b-1] = c
dp = [0] * (4*(m+1)*(n+1))
def ind(i,j,k): 
    return 4*(m+1)*i + 4*j + k
for i in range(n):
    for j in range(m):
        for k in range(3)[::-1]:
            dp[ind(i,j,k+1)] = max(dp[ind(i,j,k+1)], dp[ind(i,j,k)] + value[i][j])
        for k in range(4):
            dp[ind(i+1,j,0)] = max(dp[ind(i+1,j,0)], dp[ind(i,j,k)])
            dp[ind(i,j+1,k)] = max(dp[ind(i,j+1,k)], dp[ind(i,j,k)])
# print(dp)
mx = 0
for k in range(4):
    mx = max(mx, dp[ind(n-1,m-1,k)])
print(mx)
# Original solution
import bisect, copy, heapq, math, sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
def celi(a,b):
    return -(-a//b)
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

def main():
    r,c,k=list(map(int,input().split()))
    rcv=[list(map(int,input().split())) for i in range(k)]

    dpm=[[0]*4 for i in range(c+1)]
    dpn=[[0]*4 for i in range(c+1)]

    dic={}
    for i in range(k):
        r1,c1,v=rcv[i]
        dic[(r1,c1)]=v

    for i in range(r):
        for j in range(c):
            dpn[j+1][0]=max(dpn[j+1][0],max(dpm[j+1]))
            if (i+1,j+1) in dic:
                for k in range(3)[::-1]:
                    dpn[j+1][k+1]=max(dpn[j+1][k]+dic[(i+1,j+1)],dpn[j][k]+dic[(i+1,j+1)])
            for k in range(4):
                dpn[j+1][k]=max(dpn[j+1][k],dpn[j][k])
        # print(dpn)
        dpm=copy.deepcopy(dpn)
        dpn=[[0]*4 for i in range(c+1)]
    print((max(dpm[-1])))

main()

# Optimized solution
import bisect, copy, heapq, math, sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
def celi(a,b):
    return -(-a//b)
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

def main():
    r,c,k=list(map(int,input().split()))
    rcv=[list(map(int,input().split())) for i in range(k)]

    dpn=[[0]*4 for i in range(c+1)]

    dic={}
    for i in range(k):
        r1,c1,v=rcv[i]
        dic[(r1,c1)]=v

    for i in range(r):
        for j in range(c):
            dpn[j+1][0]=max(dpn[j+1][0],max(dpn[j+1]))
            if (i+1,j+1) in dic:
                for k in range(3)[::-1]:
                    dpn[j+1][k+1]=max(dpn[j+1][k]+dic[(i+1,j+1)],dpn[j][k]+dic[(i+1,j+1)])
            for k in range(4):
                dpn[j+1][k]=max(dpn[j+1][k],dpn[j][k])
        # print(dpn)
    print((max(dpn[-1])))

main()
# Original solution
import copy
R, C, K = list(map(int,input().split()))
i = [list(map(int,input().split())) for k in range(K)]
dp0 = [[0] * (C+1) for r in range(R+1)]
dp1 = copy.deepcopy(dp0)
dp2 = copy.deepcopy(dp0)
dp3 = copy.deepcopy(dp0)
item = copy.deepcopy(dp0)
for k in range(K):
   item[i[k][0]-1][i[k][1]-1] = i[k][2]
for r in range(R):
   for c in range(C):
      dp3[r][c] = max(dp3[r][c], dp2[r][c] + item[r][c])
      dp2[r][c] = max(dp2[r][c], dp1[r][c] + item[r][c])
      dp1[r][c] = max(dp1[r][c], dp0[r][c] + item[r][c])
      dp1[r][c+1] = max(dp1[r][c], dp1[r][c+1])
      dp2[r][c+1] = max(dp2[r][c], dp2[r][c+1])
      dp3[r][c+1] = max(dp3[r][c], dp3[r][c+1])
      dp0[r+1][c] = max(dp0[r+1][c], dp1[r][c])
      dp0[r+1][c] = max(dp0[r+1][c], dp2[r][c])
      dp0[r+1][c] = max(dp0[r+1][c], dp3[r][c])
ans = max(dp0[R-1][C-1], dp1[R-1][C-1])
ans = max(ans, dp3[R-1][C-1])
ans = max(ans, dp2[R-1][C-1])
print(ans)

# Optimized solution
import sys
import copy
R, C, K = list(map(int, input().split()))
item = [[0] * (C + 1) for _ in range(R + 1)]  # dp配列と合わせるために, 0行目, 0列目を追加している.
for s in sys.stdin.readlines():
    r, c, v = list(map(int, s.split()))
    r -= 1
    c -= 1
    item[r][c] = v
    
dp0 = [[0] * (C+1) for r in range(R+1)]
dp1 = [[0] * (C+1) for r in range(R+1)]
dp2 = [[0] * (C+1) for r in range(R+1)]
dp3 = [[0] * (C+1) for r in range(R+1)]
 
for r in range(R):
   for c in range(C):
      dp3[r][c] = max(dp3[r][c], dp2[r][c] + item[r][c])
      dp2[r][c] = max(dp2[r][c], dp1[r][c] + item[r][c])
      dp1[r][c] = max(dp1[r][c], dp0[r][c] + item[r][c])
      dp1[r][c+1] = max(dp1[r][c], dp1[r][c+1])
      dp2[r][c+1] = max(dp2[r][c], dp2[r][c+1])
      dp3[r][c+1] = max(dp3[r][c], dp3[r][c+1])
      dp0[r+1][c] = max(dp0[r+1][c], dp1[r][c])
      dp0[r+1][c] = max(dp0[r+1][c], dp2[r][c])
      dp0[r+1][c] = max(dp0[r+1][c], dp3[r][c])
ans = max(dp0[R-1][C-1], dp1[R-1][C-1])
ans = max(ans, dp3[R-1][C-1])
ans = max(ans, dp2[R-1][C-1])
print(ans)
# Original solution
import sys

inp = [int(x) for x in sys.stdin.read().split()]; ii = 0

rows, cols, k = inp[ii:ii+3]; ii += 3
items = [[] for _ in range(rows+1)]
best = [0]*(cols+1)
for _ in range(k):
	r, c, v = inp[ii:ii+3]; ii += 3
	items[r].append([c, v])
for i in range(rows+1):
	items[i].sort()
ans = 0
for r in range(1, rows+1):
	dp = []
	best1, best2 = 0, 0
	Row = items[r]
	for c, v in Row:
		v1 = best[c] + v
		v2 = best1 + v
		v3 = best2 + v
		V = v1
		if V < v2:
			V = v2
		if V < v3:
			V = v3
		dp.append(V)
		if v1 > best1:
			best1 = v1
		if v2 > best2:
			best2 = v2
		if ans < V:
			ans = V
	for j in range(len(dp)):
		if best[Row[j][0]] < dp[j]:
			best[Row[j][0]] = dp[j]
	for j in range(2, cols+1):
		if best[j] < best[j-1]:
			best[j] = best[j-1]
print(ans)


# Optimized solution
import sys

inp = [int(x) for x in sys.stdin.read().split()]; ii = 0
shift = int(10**9 + 1)
rows, cols, k = inp[ii:ii+3]; ii += 3
items = [[] for _ in range(rows+1)]
best = [0]*(cols+1)
for _ in range(k):
	r, c, v = inp[ii:ii+3]; ii += 3
	items[r].append(c*shift+v)
for i in range(rows+1):
	items[i].sort()
ans = 0
for r in range(1, rows+1):
	dp = []
	best1, best2 = 0, 0
	Row = items[r]
	for X in Row:
		c, v = X//shift, X%shift
		v1 = best[c] + v
		v2 = best1 + v
		v3 = best2 + v
		V = v1
		if V < v2:
			V = v2
		if V < v3:
			V = v3
		dp.append(V)
		if v1 > best1:
			best1 = v1
		if v2 > best2:
			best2 = v2
		if ans < V:
			ans = V
	for j in range(len(dp)):
		c = Row[j]//shift
		if best[c] < dp[j]:
			best[c] = dp[j]
	for j in range(2, cols+1):
		if best[j] < best[j-1]:
			best[j] = best[j-1]
print(ans)
# Original solution
import sys
input = sys.stdin.buffer.readline

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

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

    for r in range(R):
        for c in range(C):
            for n in range(4):
                if dp[(c+1)*(R+1)+r][n] > dp[(c+1)*(R+1)+r+1][0]:
                    dp[(c+1)*(R+1)+r+1][0] = dp[(c+1)*(R+1)+r][n]
                if dp[(c+1)*(R+1)+r][n] + State[c][r] > dp[(c+1)*(R+1)+r+1][1]:
                    dp[(c+1)*(R+1)+r+1][1] = dp[(c+1)*(R+1)+r][n] + State[c][r]
                if dp[c*(R+1)+r+1][n] > dp[(c+1)*(R+1)+r+1][n]:
                    dp[(c+1)*(R+1)+r+1][n] = dp[c*(R+1)+r+1][n]
                if n < 3 and dp[c*(R+1)+r+1][n] + State[c][r] > dp[(c+1)*(R+1)+r+1][n+1]:
                    dp[(c+1)*(R+1)+r+1][n+1] = dp[c*(R+1)+r+1][n] + State[c][r]
        
    print((max(dp[C*(R+1)+R])))

if __name__ == "__main__":
    main()

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

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

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

    for r in range(R):
        ndp = [[0]*4 for _ in range(C+1)]
        for c in range(C):
            ndp[c+1][0] = max(ndp[c+1][0], max(dp[c+1]))
            ndp[c+1][1] = ndp[c+1][0] + State[c][r]
            for n in range(4):
                if ndp[c][n] > ndp[c+1][n]:
                    ndp[c+1][n] = ndp[c][n]
                if n < 3 and ndp[c][n] + State[c][r] > ndp[c+1][n+1]:
                    ndp[c+1][n+1] = ndp[c][n] + State[c][r]
        dp = ndp
        
    print((max(dp[C])))

if __name__ == "__main__":
    main()
# Original solution
import sys
input = sys.stdin.readline
def solve():
  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
  dp = [[0]*4 for _ in range((R+1)*5000)]
  for i in range(1,R+1):
    for j in range(1,C+1):
      for k in range(4): #横から取らない
        dp[i*5000+j][k] = dp[i*5000+j-1][k]
      #上から取らない
      dp[i*5000+j][0] = max(dp[i*5000+j][0],max(dp[(i-1)*5000+j]))
      if item[i-1][j-1]>0:
        #上からとる
        dp[i*5000+j][1] = max(dp[i*5000+j][1],max(dp[(i-1)*5000+j])+item[i-1][j-1])
        for k in range(1,4): #横から取る
          dp[i*5000+j][k] = max(dp[i*5000+j][k],dp[i*5000+j-1][k-1]+item[i-1][j-1])
  ans = max(dp[R*5000+C])
  return ans
print((solve()))

# Optimized solution
import sys
input = sys.stdin.readline
def solve():
  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
  dp = [[[0]*(C+1) for _ in range(R+1)] for _ in range(4)]
  for i in range(1,R+1):
    for j in range(1,C+1):
      for k in range(4): #横から取らない
        dp[k][i][j] = dp[k][i][j-1]
      #上から取らない
      dp[0][i][j] = max(dp[0][i][j],dp[-1][i-1][j])
      if item[i-1][j-1]>0:
        #上からとる
        dp[1][i][j] = max(dp[1][i][j],dp[-1][i-1][j]+item[i-1][j-1])
        for k in range(1,4): #横から取る
          dp[k][i][j] = max(dp[k][i][j],dp[k-1][i][j-1]+item[i-1][j-1])
      for k in range(1,4):
        dp[k][i][j] = max(dp[k-1][i][j],dp[k][i][j])
  ans = 0
  for k in range(4):
    ans = max(ans,dp[k][-1][-1])
  return ans
print((solve()))
# Original solution
import sys
input = sys.stdin.readline

R,C,K=list(map(int,input().split()))
itemMap = [[0]*(C+1) for _ in range(R+1)]
dp =[[[0]*(4) for _ in range(C+1)] for _ in range(R+1)]

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

for ir in range(R):
    for ic in range(C):
        for k in range(2,-1,-1):
            #-拾う拾わない遷移-#
            dp[ir][ic][k+1] = max(dp[ir][ic][k+1],dp[ir][ic][k]+itemMap[ir][ic])
        #-位置遷移-#
        for k in range(4):
            dp[ir+1][ic][0] = max(dp[ir+1][ic][0],dp[ir][ic][k])
            dp[ir][ic+1][k] = max(dp [ir][ic+1][k],dp[ir][ic][k])

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


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

R,C,K=list(map(int,input().split()))
itemMap = [[0]*(C+1) for _ in range(R+1)]
dp =[[[0]*(C+1) for _ in range(R+1)] for _ in range(4)]

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

for ir in range(R):
    for ic in range(C):
        for k in range(2,-1,-1):
            #-拾う拾わない遷移-#
            dp[k+1][ir][ic] = max(dp[k+1][ir][ic],dp[k][ir][ic]+itemMap[ir][ic])
        #-位置遷移-#
        for k in range(4):
            dp[0][ir+1][ic] = max(dp[0][ir+1][ic],dp[k][ir][ic])
            dp[k][ir][ic+1] = max(dp[k][ir][ic+1],dp[k][ir][ic])

ans = 0
for k in range(4):
    ans = max(ans,dp[k][R-1][C-1])
print(ans)
# Original solution
import sys
input = sys.stdin.readline
def main(R,C,K,rcv):
  inf=float('inf')
  dp0=[[-inf,-inf,-inf,0] for _ in range(C)]
  item=[[0]*C for _ in range(R)]
  for r,c,v in rcv:
    item[r-1][c-1]=v
  # dp0[c][j]:c列目の時点で残りちょうどj個取れる時の最大値
  for i in range(R):
    # i+1行目に対する操作
    # 初期化
    for j in range(C):
      dp0[j][3]=max(dp0[j])
      dp0[j][2]=-inf
      dp0[j][1]=-inf
      dp0[j][0]=-inf
    for j in range(C):
      if j>0:
        dp0[j][0]=max(dp0[j][0],dp0[j-1][0])
        dp0[j][1]=dp0[j-1][1]
        dp0[j][2]=dp0[j-1][2]
      if item[i][j]>0:
        v=item[i][j]
        dp0[j][0]=max(dp0[j][0],dp0[j][1]+v)
        dp0[j][1]=max(dp0[j][1],dp0[j][2]+v)
        dp0[j][2]=max(dp0[j][2],dp0[j][3]+v)
  print((max(dp0[-1])))
if __name__=='__main__':
  R,C,K=list(map(int,input().split()))
  rcv=[list(map(int,input().split())) for _ in range(K)]
  main(R,C,K,rcv)


# Optimized solution
import sys
input = sys.stdin.readline
def main(R,C,K,rcv):
  inf=float('inf')
  dp0=[[-inf,-inf,-inf,0] for _ in range(C)]
  item=[[0]*C for _ in range(R)]
  for r,c,v in rcv:
    item[r-1][c-1]=v
  # dp0[c][j]:c列目の時点で残りちょうどj個取れる時の最大値
  for i in range(R):
    # i+1行目に対する操作
    # 遷移
    for j in range(C):
      if j>0:
        dp0[j][3]=max(dp0[j])
        dp0[j][0]=dp0[j-1][0]
        dp0[j][1]=dp0[j-1][1]
        dp0[j][2]=dp0[j-1][2]
      else:
        dp0[0][3]=max(dp0[0])
        dp0[0][2]=-inf
        dp0[0][1]=-inf
        dp0[0][0]=-inf 
      if item[i][j]>0:
        v=item[i][j]
        dp0[j][0]=max(dp0[j][0],dp0[j][1]+v)
        dp0[j][1]=max(dp0[j][1],dp0[j][2]+v)
        dp0[j][2]=max(dp0[j][2],dp0[j][3]+v)
  print((max(dp0[-1])))
if __name__=='__main__':
  R,C,K=list(map(int,input().split()))
  rcv=[list(map(int,input().split())) for _ in range(K)]
  main(R,C,K,rcv)
# Original solution
import sys
input = sys.stdin.readline
def main(R,C,K,rcv):
  inf=float('inf')
  dp0=[[-inf,-inf,-inf,0] for _ in range(C)]
  item=[[0]*C for _ in range(R)]
  for r,c,v in rcv:
    item[r-1][c-1]=v
  # dp0[c][j]:c列目の時点で残りちょうどj個取れる時の最大値
  for i in range(R):
    # i+1行目に対する操作
    # 遷移
    for j in range(C):
      if j>0:
        dp0[j][3]=max(dp0[j])
        dp0[j][0]=dp0[j-1][0]
        dp0[j][1]=dp0[j-1][1]
        dp0[j][2]=dp0[j-1][2]
      else:
        dp0[0][3]=max(dp0[0])
        dp0[0][2]=-inf
        dp0[0][1]=-inf
        dp0[0][0]=-inf 
      if item[i][j]>0:
        v=item[i][j]
        dp0[j][0]=max(dp0[j][0],dp0[j][1]+v)
        dp0[j][1]=max(dp0[j][1],dp0[j][2]+v)
        dp0[j][2]=max(dp0[j][2],dp0[j][3]+v)
  print((max(dp0[-1])))
if __name__=='__main__':
  R,C,K=list(map(int,input().split()))
  rcv=[list(map(int,input().split())) for _ in range(K)]
  main(R,C,K,rcv)


# Optimized solution
R,C,K=list(map(int,input().split()))
rcv=[list(map(int,input().split())) for _ in range(K)]
mat=[[0]*C for _ in range(R)]
for r,c,v in rcv:
  mat[r-1][c-1]=v
dp=[0]*C
for i in range(R):
  ndp=[0]*C
  wdp=[0]*4
  for j in range(C):
    wdp[0]=max(wdp[0],dp[j])
    if mat[i][j]>0:
      v=mat[i][j]
      wdp[3]=max(wdp[3],wdp[2]+v)
      wdp[2]=max(wdp[2],wdp[1]+v)
      wdp[1]=max(wdp[1],wdp[0]+v)
    ndp[j]=max(wdp)
  dp=ndp.copy()
print((max(wdp)))