CodeEff/ECCO huggingface dataset:
# Original solution
"""
dp[i][j][k] => i行目、j列のマスまで見る。k個取る時の最高値。
"""
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)]

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

            #上から降りてくる場合の価値を求める
            if i != 0:
                #i行目j列のアイテムを取らない場合
                dp[i][j][0] = max(dp[i-1][j])
                #i行目j列のアイテムを取る場合
                if v!=0:
                    dp[i][j][1] = max(dp[i-1][j]) + v

            #左から入ってくる場合の価値を求める
            if j != 0:
                if v == 0:
                    for k in range(4):
                        dp[i][j][k] = max(dp[i][j][k],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],dp[i][j-1][k-1]+v)
        if i > 0:
            tmp = dp[i-1]
            dp[i-1] = []
            del(tmp)
    print((max(dp[-1][-1])))
main()

# Optimized solution
"""
dp[i][j][k] => i行目、j列のマスまで見る。k個取る時の最高値。
"""
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 i in range(R):
        for j in range(C):
            v = items[i][j]
            if i == 0 and j == 0 and v != 0:
                dp[j][1] = v
                continue
            
            if i != 0:
                #上から降りてくる場合の価値を求める
                #i行目j列のアイテムを取らない場合
                dp[j][0] = max(dp[j])
                #i行目j列のアイテムを取る場合
                if v!=0:
                    dp[j][1] = dp[j][0] + v

            #左から入ってくる場合の価値を求める
            if j != 0:
                dp[j][0] = max(dp[j][0],dp[j-1][0])
                if v == 0:
                    for k in range(1,4):
                        dp[j][k] = max(dp[j][k],dp[j-1][k])
                else:
                    for k in range(1,4):
                        dp[j][k] = max(dp[j][k],dp[j-1][k],dp[j-1][k-1]+v)
    print((max(dp[-1])))
main()
# Original solution
"""
dp[i][j][k] => i行目j列到達時点での最大価値。i行目において拾えるアイテムの数はK個。
"""
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)]

    for i in range(R):
        for j in range(C):
            v = items[i][j]

            #上から入るパターン
            dp[i][j][0] = max(dp[i-1][j])
            if v:
                dp[i][j][1] = dp[i][j][0]+v
            
            #左から入ってくるパターン
            if j > 0:
                for k in range(4):
                    #このマスのアイテムをとらないパターン
                    dp[i][j][k] = max(dp[i][j][k],dp[i][j-1][k])
                    if v and k>0:
                        dp[i][j][k] = max(dp[i][j][k],dp[i][j-1][k-1]+v)

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

# Optimized solution
"""
dp[i][j][k] => i行目j列到達時点での最大価値。i行目において拾えるアイテムの数はK個。
"""
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 i in range(R):
        for j in range(C):
            v = items[i][j]

            #上から入るパターン
            dp[j][0] = max(dp[j])
            if v:
                dp[j][1] = dp[j][0]+v
            
            #左から入ってくるパターン
            if j > 0:
                for k in range(4):
                    #このマスのアイテムをとらないパターン
                    dp[j][k] = max(dp[j][k],dp[j-1][k])
                    if v and k>0:
                        dp[j][k] = max(dp[j][k],dp[j-1][k-1]+v)

    print((max(dp[-1])))
main()
# Original solution
R,C,K = list(map(int,input().split()))
V = [[0 for c in range(C+1)] for r in range(R+1)]
r_list = [False for r in range(R+1)]
c_list = [False for c in range(C+1)]
for i in range(K):
	r,c,v = list(map(int,input().split()))
	V[r][c] = v
	r_list[r] = True
	c_list[c] = True


r_map = {}
cnt = 0
for i in range(R+1):
	if r_list[i]:	
		cnt += 1
		r_map[i] = cnt
r_len = cnt

c_map = {}
cnt = 0
for i in range(C+1):
	if c_list[i]:
		cnt += 1
		c_map[i] = cnt
c_len = cnt

new_v = [[0 for i in range(c_len+1)] for j in range(r_len+1)]
for r in range(R+1):
	for c in range(C+1):
		if V[r][c] > 0:
			new_v[r_map[r]][c_map[c]] = V[r][c]

V = new_v
R = r_len
C = c_len

dp = [[[0 for i in range(4)] for j in range(C+1)] for k in range(R+1)]
for r in range(1, R+1):
	for c in range(1, C+1):
		v = V[r][c]
		under_val = max(dp[r-1][c])
		dp[r][c][0] = max(under_val, dp[r][c-1][0])
		if v > 0:
			dp[r][c][1] = max(under_val + v, dp[r][c-1][0] + v, dp[r][c-1][1])
			dp[r][c][2] = max(dp[r][c-1][1] + v, dp[r][c-1][2])
			dp[r][c][3] = max(dp[r][c-1][2] + v, dp[r][c-1][3])
		else:
			dp[r][c][1] = dp[r][c-1][1]
			dp[r][c][2] = dp[r][c-1][2]
			dp[r][c][3] = dp[r][c-1][3]
print((max(dp[-1][-1])))

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

dp = [[0 for i in range(4)] for j in range(C+1)]
for r in range(1, R+1):
	for c in range(1, C+1):
		v = V[r][c]
		under_val = max(dp[c])
		dp[c][0] = max(under_val, dp[c-1][0])
		if v > 0:
			dp[c][1] = max(under_val + v, dp[c-1][0] + v, dp[c-1][1])
			dp[c][2] = max(dp[c-1][1] + v, dp[c-1][2])
			dp[c][3] = max(dp[c-1][2] + v, dp[c-1][3])
		else:
			dp[c][1] = dp[c-1][1]
			dp[c][2] = dp[c-1][2]
			dp[c][3] = dp[c-1][3]
print((max(dp[-1])))
# Original solution
def e_picking_goods():
    R, C, K = [int(i) for i in input().split()]
    Goods = [[0] * (C + 1) for _ in range(R + 1)]
    for _ in range(K):
        r, c, v = [int(i) for i in input().split()]
        Goods[r][c] = v

    # dp[i][j][k]: マス (i, j) まで来たとき、その時点で i 行目のアイテムは k 個回収している
    # 場合の、回収したアイテムの価値の総和の最大値
    dp = [[[0] * 4 for j in range(C + 1)] for i in range(R + 1)]
    for i in range(R + 1):
        for j in range(C + 1):
            for k in range(4):
                # 下へ行く
                if i - 1 >= 0:
                    # 行を変えるので、k は 0 にリセットされる
                    dp[i][j][0] = max(dp[i][j][0], dp[i - 1][j][k])  # (i, j) のアイテムを拾わない
                    dp[i][j][1] = max(dp[i][j][1], dp[i - 1][j][k] + Goods[i][j])  # 拾う

                # 右へ行く
                if j - 1 >= 0:
                    dp[i][j][k] = max(dp[i][j][k], dp[i][j - 1][k])  # 拾わない
                    if k - 1 >= 0:
                        dp[i][j][k] = max(dp[i][j][k], dp[i][j - 1][k - 1] + Goods[i][j])  # まだ拾えるし、拾う
    return max(dp[R][C][k] for k in range(4))

print((e_picking_goods()))

# Optimized solution
def e_picking_goods():
    # 参考: https://atcoder.jp/contests/abc175/submissions/16044254
    R, C, K = [int(i) for i in input().split()]
    Goods = [[0] * (C + 1) for _ in range(R + 1)]
    for _ in range(K):
        r, c, v = [int(i) for i in input().split()]
        Goods[r][c] = v

    # editorial に対し、行の情報を除去する
    dp = [[0] * 4 for _ in range(C + 1)]
    for i in range(1, R + 1):
        dp_next = [[0] * 4 for _ in range(C + 1)]
        for j in range(1, C + 1):
            up_max = max(dp[j])  # 上のマスで 0~3 回アイテムを拾っていたときの、価値の最大値
            v = Goods[i][j]

            # 左か上から来て、アイテムを拾わない
            dp_next[j][0] = max(up_max, dp_next[j - 1][0])
            # 上から来て拾う or 左から来て拾う or 左から来て拾わない
            dp_next[j][1] = max(up_max + v, dp_next[j - 1][0] + v, dp_next[j - 1][1])
            # 左から来て k-1 個拾っており、ここで拾う or k 個拾っており、ここで拾わない
            for k in range(2, 4):
                dp_next[j][k] = max(dp_next[j - 1][k - 1] + v, dp_next[j - 1][k])
        dp = dp_next  # 次の行へ注目を移す
    return max(dp[-1])

print((e_picking_goods()))
# Original solution
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    R, C, K, *RCV = list(map(int, read().split()))

    item = dict()
    for r, c, v in zip(*[iter(RCV)] * 3):
        item[(r - 1, c - 1)] = v

    dp = [0] * (C + 1)
    for i in range(R):
        dp, dp_prev = [0] * (C + 1), dp
        v = [0] * 4
        for j in range(C):
            for k in range(4):
                if v[k] < dp_prev[j + 1]:
                    v[k] = dp_prev[j + 1]
            if (i, j) in item:
                for k in range(2, -1, -1):
                    if v[k + 1] < v[k] + item[(i, j)]:
                        v[k + 1] = v[k] + item[(i, j)]
            dp[j + 1] = v[3]

    print((dp[C]))

    return


if __name__ == '__main__':
    main()


# Optimized solution
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    R, C, K, *RCV = list(map(int, read().split()))

    item = [[0] * C for _ in range(R)]
    for r, c, v in zip(*[iter(RCV)] * 3):
        item[r - 1][c - 1] = v

    dp = [0] * (C + 1)
    for i in range(R):
        dp, dp_prev = [0] * (C + 1), dp
        v = [0] * 4
        for j in range(C):
            for k in range(4):
                if v[k] < dp_prev[j + 1]:
                    v[k] = dp_prev[j + 1]
            if item[i][j] > 0:
                for k in range(2, -1, -1):
                    if v[k + 1] < v[k] + item[i][j]:
                        v[k + 1] = v[k] + item[i][j]
            dp[j + 1] = v[3]

    print((dp[C]))

    return


if __name__ == '__main__':
    main()
# Original solution
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    R, C, K, *RCV = list(map(int, read().split()))

    item = [[0] * C for _ in range(R)]
    for r, c, v in zip(*[iter(RCV)] * 3):
        item[r - 1][c - 1] = v

    dp = [0] * (C + 1)
    for i in range(R):
        dp, dp_prev = [0] * (C + 1), dp
        v = [0] * 4
        for j in range(C):
            for k in range(4):
                if v[k] < dp_prev[j + 1]:
                    v[k] = dp_prev[j + 1]
            if item[i][j] > 0:
                for k in range(2, -1, -1):
                    if v[k + 1] < v[k] + item[i][j]:
                        v[k + 1] = v[k] + item[i][j]
            dp[j + 1] = v[3]

    print((dp[C]))

    return


if __name__ == '__main__':
    main()


# Optimized solution
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    R, C, K, *RCV = list(map(int, read().split()))

    item = [[0] * C for _ in range(R)]
    for r, c, v in zip(*[iter(RCV)] * 3):
        item[r - 1][c - 1] = v

    dp = [0] * (C + 1)
    for i in range(R):
        dp, dp_prev = [0] * (C + 1), dp
        v = [0] * 4
        for j in range(C):
            for k in range(4):
                if v[k] < dp_prev[j + 1]:
                    v[k] = dp_prev[j + 1]
                else:
                    break
            if item[i][j] > 0:
                for k in range(2, -1, -1):
                    if v[k + 1] < v[k] + item[i][j]:
                        v[k + 1] = v[k] + item[i][j]
            dp[j + 1] = v[3]

    print((dp[C]))

    return


if __name__ == '__main__':
    main()
# Original solution
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    R, C, K, *RCV = list(map(int, read().split()))

    item = [[0] * C for _ in range(R)]
    for r, c, v in zip(*[iter(RCV)] * 3):
        item[r - 1][c - 1] = v

    dp = [0] * (C + 1)
    for i in range(R):
        dp, dp_prev = [0] * (C + 1), dp
        v = [0] * 4
        for j in range(C):
            for k in range(4):
                if v[k] < dp_prev[j + 1]:
                    v[k] = dp_prev[j + 1]
                else:
                    break
            if item[i][j] > 0:
                for k in range(2, -1, -1):
                    if v[k + 1] < v[k] + item[i][j]:
                        v[k + 1] = v[k] + item[i][j]
            dp[j + 1] = v[3]

    print((dp[C]))

    return


if __name__ == '__main__':
    main()


# Optimized solution
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    R, C, K, *RCV = list(map(int, read().split()))

    item = [[0] * C for _ in range(R)]
    for r, c, v in zip(*[iter(RCV)] * 3):
        item[r - 1][c - 1] = v

    dp = [0] * (C + 1)
    for i in range(R):
        value = [0] * 4
        for j in range(C):
            for k in range(4):
                if value[k] < dp[j + 1]:
                    value[k] = dp[j + 1]
                else:
                    break
            if item[i][j] > 0:
                for k in range(2, -1, -1):
                    if value[k + 1] < value[k] + item[i][j]:
                        value[k + 1] = value[k] + item[i][j]
            dp[j + 1] = value[3]

    print((dp[C]))

    return


if __name__ == '__main__':
    main()
# Original solution
import sys
from collections import defaultdict
input=sys.stdin.readline
d=defaultdict(int)
R,C,k=list(map(int,input().split()))
for i in range(k):
  r,c,v=list(map(int,input().split()))
  d[(r-1)*C+c-1]=v
dp=[[[0,0,0,0] for j in range(C+1)] for i in range(R+1)]
for i in range(1,R+1):
  for j in range(1,C+1):
    V=d[(i-1)*C+(j-1)]
    dp[i][j][0]=max(dp[i-1][j][0],dp[i-1][j][1],dp[i-1][j][2],dp[i-1][j][3],dp[i][j-1][0])
    dp[i][j][1]=max(dp[i][j][0]+V,dp[i][j-1][1])
    dp[i][j][2]=max(dp[i][j-1][1]+V,dp[i][j-1][2])
    dp[i][j][3]=max(dp[i][j-1][2]+V,dp[i][j-1][3])
print((max(dp[-1][-1])))

# Optimized solution
import sys
input=sys.stdin.readline
R,C,k=list(map(int,input().split()))
A=[[0]*C for i in range(R)]
for i in range(k):
  r,c,v=list(map(int,input().split()))
  A[r-1][c-1]=v
dp=[[[0,0,0,0] for j in range(C+1)] for i in range(R+1)]
for i in range(1,R+1):
  for j in range(1,C+1):
    V=A[i-1][j-1]
    dp[i][j][0]=max(dp[i-1][j][0],dp[i-1][j][1],dp[i-1][j][2],dp[i-1][j][3],dp[i][j-1][0])
    dp[i][j][1]=max(dp[i][j][0]+V,dp[i][j-1][1])
    dp[i][j][2]=max(dp[i][j-1][1]+V,dp[i][j-1][2])
    dp[i][j][3]=max(dp[i][j-1][2]+V,dp[i][j-1][3])
print((max(dp[-1][-1])))
# Original solution
import sys
input=sys.stdin.readline
R,C,k=list(map(int,input().split()))
A=[[0]*C for i in range(R)]
for i in range(k):
  r,c,v=list(map(int,input().split()))
  A[r-1][c-1]=v
dp=[[[0,0,0,0] for j in range(C+1)] for i in range(R+1)]
for i in range(1,R+1):
  for j in range(1,C+1):
    V=A[i-1][j-1]
    dp[i][j][0]=max(dp[i-1][j][0],dp[i-1][j][1],dp[i-1][j][2],dp[i-1][j][3],dp[i][j-1][0])
    dp[i][j][1]=max(dp[i][j][0]+V,dp[i][j-1][1])
    dp[i][j][2]=max(dp[i][j-1][1]+V,dp[i][j-1][2])
    dp[i][j][3]=max(dp[i][j-1][2]+V,dp[i][j-1][3])
print((max(dp[-1][-1])))

# Optimized solution
import sys
input=sys.stdin.readline
R,C,k=list(map(int,input().split()))
A=[[0]*C for i in range(R)]
for i in range(k):
  r,c,v=list(map(int,input().split()))
  A[r-1][c-1]=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=A[i-1][j-1]
    dp0[i][j]=max(dp0[i-1][j],dp1[i-1][j],dp2[i-1][j],dp3[i-1][j],dp0[i][j-1])
    dp1[i][j]=max(dp0[i][j]+V,dp1[i][j-1])
    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[-1][-1],dp1[-1][-1],dp2[-1][-1],dp3[-1][-1])))
# Original solution
import sys
input=lambda: sys.stdin.readline().rstrip()
import collections
D=collections.defaultdict(int)
r,c,k=list(map(int,input().split()))
for _ in range(k):
	ri,ci,v=list(map(int,input().split()))
	ri-=1
	ci-=1
	D[ri*10**5+ci]=v

DP=[[[0]*4 for _ in range(c+1)] for i in range(r+1)]
for i in range(r+1):
	for j in range(c+1):
		v=D[i*10**5+j]
		if v!=0:
			DP[i][j][1]=max(DP[i-1][j])+v
		for ii in range(4):
			DP[i][j][0]=max(DP[i][j][0],DP[i-1][j][ii])
			if v!=0:
				DP[i][j][1]=max(DP[i][j][1],DP[i-1][j][ii]+v)
			DP[i][j][ii]=max(DP[i][j][ii],DP[i][j-1][ii])
			if v!=0 and ii!=0:
				DP[i][j][ii]=max(DP[i][j][ii],DP[i][j-1][ii-1]+v)
		
ans=max(DP[r-1][c-1])
print(ans)



# Optimized solution
import sys
input=lambda: sys.stdin.readline().rstrip()
import collections
D=collections.defaultdict(int)
r,c,k=list(map(int,input().split()))
for _ in range(k):
	ri,ci,v=list(map(int,input().split()))
	ri-=1
	ci-=1
	D[ri*10**5+ci]=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(r+1):
	for j in range(c+1):
		v=D[i*10**5+j]
		if v!=0:
			DP1[i][j]=max(DP0[i-1][j],DP1[i-1][j],DP2[i-1][j],DP3[i-1][j])+v

		DP0[i][j]=max(DP0[i][j],DP0[i-1][j],DP1[i-1][j],DP2[i-1][j],DP3[i-1][j])
		if v!=0:
			DP1[i][j]=max(DP1[i][j],DP0[i-1][j]+v,DP1[i-1][j]+v,DP2[i-1][j]+v,DP3[i-1][j]+v)
		DP0[i][j]=max(DP0[i][j],DP0[i][j-1])
		DP1[i][j]=max(DP1[i][j],DP1[i][j-1])
		DP2[i][j]=max(DP2[i][j],DP2[i][j-1])
		DP3[i][j]=max(DP3[i][j],DP3[i][j-1])
		if v!=0:
			DP1[i][j]=max(DP1[i][j],DP0[i][j-1]+v)
			DP2[i][j]=max(DP2[i][j],DP1[i][j-1]+v)
			DP3[i][j]=max(DP3[i][j],DP2[i][j-1]+v)
		
ans=max(DP0[r-1][c-1],DP1[r-1][c-1],DP2[r-1][c-1],DP3[r-1][c-1])
print(ans)
# Original solution
import sys
input=lambda: sys.stdin.readline().rstrip()
import collections
D=collections.defaultdict(int)
r,c,k=list(map(int,input().split()))
for _ in range(k):
	ri,ci,v=list(map(int,input().split()))
	ri-=1
	ci-=1
	D[ri*10**5+ci]=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(r+1):
	for j in range(c+1):
		v=D[i*10**5+j]
		if v!=0:
			DP1[i][j]=max(DP0[i-1][j],DP1[i-1][j],DP2[i-1][j],DP3[i-1][j])+v

		DP0[i][j]=max(DP0[i][j],DP0[i-1][j],DP1[i-1][j],DP2[i-1][j],DP3[i-1][j])
		if v!=0:
			DP1[i][j]=max(DP1[i][j],DP0[i-1][j]+v,DP1[i-1][j]+v,DP2[i-1][j]+v,DP3[i-1][j]+v)
		DP0[i][j]=max(DP0[i][j],DP0[i][j-1])
		DP1[i][j]=max(DP1[i][j],DP1[i][j-1])
		DP2[i][j]=max(DP2[i][j],DP2[i][j-1])
		DP3[i][j]=max(DP3[i][j],DP3[i][j-1])
		if v!=0:
			DP1[i][j]=max(DP1[i][j],DP0[i][j-1]+v)
			DP2[i][j]=max(DP2[i][j],DP1[i][j-1]+v)
			DP3[i][j]=max(DP3[i][j],DP2[i][j-1]+v)
		
ans=max(DP0[r-1][c-1],DP1[r-1][c-1],DP2[r-1][c-1],DP3[r-1][c-1])
print(ans)



# Optimized solution
import sys
input=lambda: sys.stdin.readline().rstrip()

r,c,k=list(map(int,input().split()))
D=[[0]*c for _ in range(r)] 
for _ in range(k):
	ri,ci,v=list(map(int,input().split()))
	ri-=1
	ci-=1
	D[ri][ci]=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(r):
	for j in range(c):
		v=D[i][j]
		if v!=0:
			DP1[i][j]=max(DP0[i-1][j],DP1[i-1][j],DP2[i-1][j],DP3[i-1][j])+v

		DP0[i][j]=max(DP0[i][j],DP0[i-1][j],DP1[i-1][j],DP2[i-1][j],DP3[i-1][j])
		if v!=0:
			DP1[i][j]=max(DP1[i][j],DP0[i-1][j]+v,DP1[i-1][j]+v,DP2[i-1][j]+v,DP3[i-1][j]+v)
		DP0[i][j]=max(DP0[i][j],DP0[i][j-1])
		DP1[i][j]=max(DP1[i][j],DP1[i][j-1])
		DP2[i][j]=max(DP2[i][j],DP2[i][j-1])
		DP3[i][j]=max(DP3[i][j],DP3[i][j-1])
		if v!=0:
			DP1[i][j]=max(DP1[i][j],DP0[i][j-1]+v)
			DP2[i][j]=max(DP2[i][j],DP1[i][j-1]+v)
			DP3[i][j]=max(DP3[i][j],DP2[i][j-1]+v)
		
ans=max(DP0[r-1][c-1],DP1[r-1][c-1],DP2[r-1][c-1],DP3[r-1][c-1])
print(ans)
# Original solution
import sys

input = sys.stdin.buffer.readline
r, c, k = list(map(int, input().split()))


graph = [[0] * (c) for _ in range(r)]

for _ in range(k):
    d, e, f = list(map(int, input().split()))
    graph[d - 1][e - 1] = f


# dijkstra
infi = 10 ** 10
money = [[[-infi] * (4) for _ in range(c)] for _ in range(r)]
money[0][0][0] = 0
for i in range(r):
    for j in range(c):
        for t in range(4):
            m = money[i][j][t]
            delta = graph[i][j]
            if i < r - 1:
                ni = i + 1
                nj = j
                nt = 0
                money[ni][nj][nt] = max(money[ni][nj][nt], m)
                if t < 3:
                    money[ni][nj][nt] = max(money[ni][nj][nt], m + delta)

            if j < c - 1:
                ni = i
                nj = j + 1
                nt = t
                money[ni][nj][nt] = max(money[ni][nj][nt], m)
                if t < 3:
                    nt = t + 1
                    money[ni][nj][nt] = max(money[ni][nj][nt], m + delta)


if graph[r - 1][c - 1] > 0:
    for t in range(3):
        money[r - 1][c - 1][t] += graph[r - 1][c - 1]
ans = max(money[r - 1][c - 1])

print(ans)


# Optimized solution
import sys

input = sys.stdin.buffer.readline
r, c, k = list(map(int, input().split()))


graph = [[0] * (c) for _ in range(r)]

for _ in range(k):
    d, e, f = list(map(int, input().split()))
    graph[d - 1][e - 1] = f


infi = 10 ** 10
money = [[[-infi] * (c) for _ in range(r)] for _ in range(4)]
money[0][0][0] = 0
for i in range(r):
    for j in range(c):
        for t in range(4):
            m = money[t][i][j]
            delta = graph[i][j]
            if i < r - 1:
                ni = i + 1
                nj = j
                nt = 0
                money[nt][ni][nj] = max(money[nt][ni][nj], m)
                if t < 3:
                    money[nt][ni][nj] = max(money[nt][ni][nj], m + delta)

            if j < c - 1:
                ni = i
                nj = j + 1
                nt = t
                money[nt][ni][nj] = max(money[nt][ni][nj], m)
                if t < 3:
                    nt = t + 1
                    money[nt][ni][nj] = max(money[nt][ni][nj], m + delta)

ans = 0
if graph[r - 1][c - 1] > 0:
    for t in range(3):
        money[t][r - 1][c - 1] += graph[r - 1][c - 1]
for i in range(4):
    ans = max(money[i][r - 1][c - 1], ans)

print(ans)
# Original solution
while 1:
	n=eval(input())
	if n==0:break
	p=list(map(int,input().split()))
	sp=p[0]
	ans=[]
	for i in range(n-1):
		if p[i]+1!=p[i+1]:
			if sp!=p[i]:
				ans.append(str(sp)+"-"+str(p[i]))
			else:
				ans.append(str(sp))
			sp=p[i+1]
	else:
		if sp!=p[-1]:
			ans.append(str(sp)+"-"+str(p[-1]))
		else:
			ans.append(str(sp))
	print(" ".join(ans))

# Optimized solution
while 1:
	n=eval(input())
	if n==0:break
	p=list(map(int,input().split()))+["end"]
	sp=p[0]
	ans=[]
	for i in range(n):
		if p[i]+1!=p[i+1]:
			if sp!=p[i]:
				ans.append(str(sp)+"-"+str(p[i]))
			else:
				ans.append(str(sp))
			sp=p[i+1]
	print(" ".join(ans))