CodeEff/ECCO huggingface dataset:
# Original solution
import sys
input = sys.stdin.readline

N=int(eval(input()))
B=sorted([list(map(int,input().split())) for i in range(N)],key=lambda x:x[0]+x[1])
#W+Sの順にソートすると無駄がない。

DP=[0]*(10**4+2)
#重さの合計がWのときの価値。
#W=10**4+1ならそれ以上更新されないので、W>=10**4+1以上のものはそこに置く

for w,s,v in B:
    
    if 10**4+1-w<=s:
        if DP[-1]<max(DP[10**4+1-w:s+1])+v:
            DP[-1]=max(DP[10**4+1-w:s+1])+v
        
    for i in range(min(10**4-w,s),-1,-1):
        if DP[i+w]<DP[i]+v:
            DP[i+w]=DP[i]+v

print((max(DP)))

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

N=int(eval(input()))
B=sorted([list(map(int,input().split())) for i in range(N)],key=lambda x:x[0]+x[1])
#W+Sの順にソートすると無駄がない。

DP=[0]*(10**4+2)
#重さの合計がWのときの価値。
#W=10**4+1ならそれ以上更新されないので、W>=10**4+1以上のものはそこに置く

for w,s,v in B:
    
    if 10**4+1-w<=s:
        x=max(DP[10**4+1-w:s+1])+v
        if DP[-1]<x:
            DP[-1]=x

    if 10**4-w<s:
        for i in range(10**4-w,-1,-1):
            if DP[i+w]<DP[i]+v:
                DP[i+w]=DP[i]+v

    else:
        for i in range(s,-1,-1):
            if DP[i+w]<DP[i]+v:
                DP[i+w]=DP[i]+v        

print((max(DP)))
# Original solution
from collections import defaultdict
import sys
input=sys.stdin.readline
r,c,k=list(map(int,input().split()))
l=[0]*((r+1)*(c+1))
for i in range(k):
  a1,a2,a3=list(map(int,input().split()))
  l[a1*(c+1)+a2]=a3
dp0=[[0 for i in range(c+1)] for j in range(r+1)]
dp1=[[0 for i in range(c+1)] for j in range(r+1)]
dp2=[[0 for i in range(c+1)] for j in range(r+1)]
dp3=[[0 for i in range(c+1)] for j in range(r+1)]
for i in range(r):
  for j in range(c):
    x=l[i*(c+1)+j+1]
    y=l[(i+1)*(c+1)+j]
    dp3[i+1][j+1]=max(dp2[i][j+1]+x,dp3[i][j+1],dp2[i+1][j]+y,dp3[i+1][j])
    dp2[i+1][j+1]=max(dp2[i][j+1]+x,dp3[i][j+1],dp1[i+1][j]+y,dp2[i+1][j])
    dp1[i+1][j+1]=max(dp2[i][j+1]+x,dp3[i][j+1],dp0[i+1][j]+y,dp1[i+1][j])
    dp0[i+1][j+1]=max(dp2[i][j+1]+x,dp3[i][j+1],dp0[i+1][j])
z=l[r*(c+1)+c]
print((max(dp2[r][c]+z,dp3[r][c])))

# Optimized solution
import sys
input=sys.stdin.readline
r,c,k=list(map(int,input().split()))
l=[0]*((r+1)*(c+1))
for i in range(k):
  a1,a2,a3=list(map(int,input().split()))
  l[a1*(c+1)+a2]=a3
dp0=[[0 for i in range(c+1)] for j in range(r+1)]
dp1=[[0 for i in range(c+1)] for j in range(r+1)]
dp2=[[0 for i in range(c+1)] for j in range(r+1)]
dp3=[[0 for i in range(c+1)] for j in range(r+1)]
for i in range(r):
  for j in range(c):
    x=l[i*(c+1)+j+1]
    y=l[(i+1)*(c+1)+j]
    dp3[i+1][j+1]=max(dp2[i][j+1]+x,dp3[i][j+1],dp2[i+1][j]+y,dp3[i+1][j])
    dp2[i+1][j+1]=max(dp2[i][j+1]+x,dp3[i][j+1],dp1[i+1][j]+y,dp2[i+1][j])
    dp1[i+1][j+1]=max(dp2[i][j+1]+x,dp3[i][j+1],dp0[i+1][j]+y,dp1[i+1][j])
    dp0[i+1][j+1]=max(dp2[i][j+1]+x,dp3[i][j+1],dp0[i+1][j])
z=l[r*(c+1)+c]
print((max(dp2[r][c]+z,dp3[r][c])))
# Original solution
import sys
mod=10**9+7 ; inf=float("inf")
from math import sqrt, ceil
from collections import deque, Counter, defaultdict #すべてのkeyが用意されてる defaultdict(int)で初期化
# input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import ROUND_HALF_UP,Decimal  #変換後の末尾桁を0や0.01で指定
  #Decimal((str(0.5)).quantize(Decimal('0'), rounding=ROUND_HALF_UP))
from functools import lru_cache
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#ソート、"a"+"b"、再帰ならPython3の方がいい
#######ここから天ぷら########

h,w,k=list(map(int,input().split()))
# R=[]
A=[[0]*w for i in range(h)]
dp=[[[0]*4 for j in range(w)] for i in range(h)]

for s in sys.stdin.readlines():
    x,y,v=list(map(int,s.split()))
    x-=1;y-=1
    A[x][y]=v
    # dp[x][y][1]=v
    # dp[x][y][2]=v
    # dp[x][y][3]=v;
dp[0][0][1]=A[0][0]
for i in range(h):
    for j in range(w):
        for k in range(4):
            here=dp[i][j][k]
            if i<h-1:
                dp[i+1][j][0] = max(here,dp[i+1][j][0])
                dp[i+1][j][1] = max(here+A[i+1][j], dp[i+1][j][1])
            if j<w-1:
                dp[i][j+1][k] = max(dp[i][j+1][k], here)
                if k<=2:
                    dp[i][j+1][k+1]= max(dp[i][j+1][k+1],here+ A[i][j+1])
           

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


# Optimized solution
import sys

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()))
    item[r][c] = v

dp = [[[0] * (C + 1) for _ in range(R + 1)] for _ in range(4)]
for i in range(R + 1):
    for j in range(C + 1):
        for k in range(4):
            here = dp[k][i][j]
            # 次の行に移動する場合
            if i + 1 <= R:
                # 移動先のアイテムを取らない場合
                dp[0][i + 1][j] = max(dp[0][i + 1][j], here)
                # 移動先のアイテムを取る場合
                dp[1][i + 1][j] = max(dp[1][i + 1][j], here + item[i + 1][j])
            # 次の列に移動する場合
            if j + 1 <= C:
                # 移動先のアイテムを取らない場合
                dp[k][i][j + 1] = max(dp[k][i][j + 1], here)
                # 現在のkが3未満のときのみ, 移動先のアイテムを取ることが可能
                if k < 3:
                    dp[k + 1][i][j + 1] = max(dp[k + 1][i][j + 1], here + item[i][j + 1])
ans = 0
for k in range(4):
    ans = max(ans, dp[k][-1][-1])
print(ans)
# Original solution
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


DP = [[[-float('inf')] * 4 for _ in range(C + 1)] for __ in range(R + 1)]

for y in range(R+1):
    for x in range(C+1):
        if y == 0:
            DP[y][x][0] = 0
            continue
        if x == 0:
            DP[y][x][0] = 0
            continue
        if Items[y][x] == 0:
            for k in range(4):
                DP[y][x][0] = max(DP[y][x][0], DP[y - 1][x][k])
                if k != 0:
                    DP[y][x][k] = DP[y][x-1][k]
            DP[y][x][0] = max(DP[y][x][0], DP[y][x-1][0])
        else:
            for k in range(4):
                DP[y][x][0] = max(DP[y][x][0], DP[y - 1][x][k])
            DP[y][x][0] = max(DP[y][x][0], DP[y][x - 1][0])
            for k in range(1, 4):
                DP[y][x][k] = max(DP[y][x-1][k-1] + Items[y][x], DP[y][x-1][k])
                if k == 1:
                    DP[y][x][k] = max(DP[y][x][k], max(DP[y-1][x]) + Items[y][x])

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

# Optimized solution
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


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

for x in range(1, C+1):
    for y in range(1, R+1):
        v = Items[y][x]
        if v:
            DP[y][3] = max(DP[y][3], DP[y][2] + v)
            DP[y][2] = max(DP[y][2], DP[y][1] + v)
            DP[y][1] = max(max(DP[y][1], DP[y][0] + v), max(DP[y-1]) + v)
            DP[y][0] = max(DP[y][0], max(DP[y-1]))
        else:
            DP[y][0] = max(DP[y][0], max(DP[y-1]))

print((max(DP[R])))
# Original solution
import os,io
import sys
input=io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
r,c,k=list(map(int,input().split()))
dp = [[[0 for y in range(c)] for z in range(r)] for P in range(4)]
m=[]
for i in range(r):
  m.append([])
  for j in range(c):
    m[i].append(0)
for i in range(k):
  ri,ci,v=list(map(int,input().split()))
  m[ri-1][ci-1]=v
dp[0][0][0]=0
dp[1][0][0]=m[0][0]
dp[2][0][0]=m[0][0]
dp[3][0][0]=m[0][0]
for i in range(r):
  for j in range(c):
    if j+1<c:
      dp[0][i][j+1]=max(dp[0][i][j+1],dp[0][i][j])
      dp[1][i][j+1]=max(dp[1][i][j],max(dp[1][i][j+1],dp[0][i][j]+m[i][j+1]))
      dp[2][i][j+1]=max(dp[2][i][j],max(dp[2][i][j+1],dp[1][i][j]+m[i][j+1]))
      dp[3][i][j+1]=max(dp[3][i][j],max(dp[3][i][j+1],dp[2][i][j]+m[i][j+1]))
    if i+1<r:
      dp[0][i+1][j]=dp[3][i][j]
      dp[1][i+1][j]=dp[3][i][j]+m[i+1][j]
      dp[2][i+1][j]=dp[3][i][j]+m[i+1][j]
      dp[3][i+1][j]=dp[3][i][j]+m[i+1][j]
print((dp[3][r-1][c-1]))
    

# Optimized solution
import os,io
import sys
input=io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
r,c,k=list(map(int,input().split()))
dp = [0]*(r*c*4)
m=[]
for i in range(r):
  m.append([])
  for j in range(c):
    m[i].append(0)
for i in range(k):
  ri,ci,v=list(map(int,input().split()))
  m[ri-1][ci-1]=v
dp[0*r*c+0*c+0]=0
dp[1*r*c+0*c+0]=m[0][0]
dp[2*r*c+0*c+0]=m[0][0]
dp[3*r*c+0*c+0]=m[0][0]
for i in range(r):
  for j in range(c):
    if j+1<c:
      dp[0*r*c+i*c+j+1]=max(dp[0*r*c+i*c+j+1],dp[0*r*c+i*c+j])
      dp[1*r*c+i*c+j+1]=max(dp[1*r*c+i*c+j],max(dp[1*r*c+i*c+j+1],dp[0*r*c+i*c+j]+m[i][j+1]))
      dp[2*r*c+i*c+j+1]=max(dp[2*r*c+i*c+j],max(dp[2*r*c+i*c+j+1],dp[1*r*c+i*c+j]+m[i][j+1]))
      dp[3*r*c+i*c+j+1]=max(dp[3*r*c+i*c+j],max(dp[3*r*c+i*c+j+1],dp[2*r*c+i*c+j]+m[i][j+1]))
    if i+1<r:
      dp[0*r*c+(i+1)*c+j]=dp[3*r*c+i*c+j]
      dp[1*r*c+(i+1)*c+j]=dp[3*r*c+i*c+j]+m[i+1][j]
      dp[2*r*c+(i+1)*c+j]=dp[3*r*c+i*c+j]+m[i+1][j]
      dp[3*r*c+(i+1)*c+j]=dp[3*r*c+i*c+j]+m[i+1][j]
print((dp[3*r*c+(r-1)*c+c-1]))
# Original solution
import os,io
import sys
input=io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
r,c,k=list(map(int,input().split()))
dp = [0]*(r*c*4)
m=[]
for i in range(r):
  m.append([])
  for j in range(c):
    m[i].append(0)
for i in range(k):
  ri,ci,v=list(map(int,input().split()))
  m[ri-1][ci-1]=v
dp[0*r*c+0*c+0]=0
dp[1*r*c+0*c+0]=m[0][0]
dp[2*r*c+0*c+0]=m[0][0]
dp[3*r*c+0*c+0]=m[0][0]
for i in range(r):
  for j in range(c):
    if j+1<c:
      dp[0*r*c+i*c+j+1]=max(dp[0*r*c+i*c+j+1],dp[0*r*c+i*c+j])
      dp[1*r*c+i*c+j+1]=max(dp[1*r*c+i*c+j],max(dp[1*r*c+i*c+j+1],dp[0*r*c+i*c+j]+m[i][j+1]))
      dp[2*r*c+i*c+j+1]=max(dp[2*r*c+i*c+j],max(dp[2*r*c+i*c+j+1],dp[1*r*c+i*c+j]+m[i][j+1]))
      dp[3*r*c+i*c+j+1]=max(dp[3*r*c+i*c+j],max(dp[3*r*c+i*c+j+1],dp[2*r*c+i*c+j]+m[i][j+1]))
    if i+1<r:
      dp[0*r*c+(i+1)*c+j]=dp[3*r*c+i*c+j]
      dp[1*r*c+(i+1)*c+j]=dp[3*r*c+i*c+j]+m[i+1][j]
      dp[2*r*c+(i+1)*c+j]=dp[3*r*c+i*c+j]+m[i+1][j]
      dp[3*r*c+(i+1)*c+j]=dp[3*r*c+i*c+j]+m[i+1][j]
print((dp[3*r*c+(r-1)*c+c-1]))
    

# Optimized solution
import os,io
input=io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
r,c,k=list(map(int,input().split()))
dp = [0]*(r*c*4)
m=[0]*(r*c)
for i in range(k):
  ri,ci,v=list(map(int,input().split()))
  m[(ri-1)*c+ci-1]=v
dp[0*r*c+0*c+0]=0
dp[1*r*c+0*c+0]=m[0]
dp[2*r*c+0*c+0]=m[0]
dp[3*r*c+0*c+0]=m[0]
for i in range(r):
  for j in range(c):
    if j+1<c:
      dp[0*r*c+i*c+j+1]=max(dp[0*r*c+i*c+j+1],dp[0*r*c+i*c+j])
      dp[1*r*c+i*c+j+1]=max(dp[1*r*c+i*c+j],max(dp[1*r*c+i*c+j+1],dp[0*r*c+i*c+j]+m[i*c+j+1]))
      dp[2*r*c+i*c+j+1]=max(dp[2*r*c+i*c+j],max(dp[2*r*c+i*c+j+1],dp[1*r*c+i*c+j]+m[i*c+j+1]))
      dp[3*r*c+i*c+j+1]=max(dp[3*r*c+i*c+j],max(dp[3*r*c+i*c+j+1],dp[2*r*c+i*c+j]+m[i*c+j+1]))
    if i+1<r:
      a=dp[3*r*c+i*c+j]
      b=a+m[(i+1)*c+j]
      dp[0*r*c+(i+1)*c+j]=a
      dp[1*r*c+(i+1)*c+j]=b
      dp[2*r*c+(i+1)*c+j]=b
      dp[3*r*c+(i+1)*c+j]=b
print((dp[3*r*c+(r-1)*c+c-1]))
# Original solution
#!/usr/bin/env python3
import sys
input = sys.stdin.readline

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

# dp[taken 0 - 2][R][C]
dp = [[-1] * (C + 1) * (R + 1) for _ in range(4)]
dp[0][0] = 0
for j in range(C):
    for i in range(R):
        for k in range(4):
            ij = i * C + j
            ij1 = i * C + j + 1
            i1j = (i + 1) * C + j
            # Use
            if field[i][j] and k < 3:
                dp[k+1][ij1] = max(dp[k+1][ij1], dp[k][ij] + field[i][j]) 
                dp[0][i1j] = max(dp[0][i1j], dp[k][ij] + field[i][j]) 
            # No use down
            dp[0][i1j] = max(dp[0][i1j], dp[k][ij]) 
            # No use right
            dp[k][ij1] = max(dp[k][ij1], dp[k][ij]) 

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

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

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

# dp[taken 0 - 2][R][C]
dp = [[-1] * (C + 1) * (R + 1) for _ in range(4)]
dp[0][0] = 0
for j in range(C):
    for i in range(R):
        for k in range(4):
            ij = i * C + j
            ij1 = ij + 1
            i1j = ij + C
            item = field[i][j]
            # Use
            if item and k < 3:
                dp[k+1][ij1] = max(dp[k+1][ij1], dp[k][ij] + item) 
                dp[0][i1j] = max(dp[0][i1j], dp[k][ij] + item) 
            # No use down
            dp[0][i1j] = max(dp[0][i1j], dp[k][ij]) 
            # No use right
            dp[k][ij1] = max(dp[k][ij1], dp[k][ij]) 

ans = 0
for i in range(4):
    for j in range(R + 1):
        ans = max(ans, dp[i][j * C + C - 1])
print(ans)
# Original solution
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return list(map(int, input().split()))
sys.setrecursionlimit(10**9)

R, C, K = mapint()
dp = [[[0]*4 for _ in range(C)] for _ in range(R)]
from collections import defaultdict
dic = [[0]*C for _ in range(R)]
for _ in range(K):
    r, c, v = mapint()
    dic[r-1][c-1] = v

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

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

# Optimized solution
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return list(map(int, input().split()))
sys.setrecursionlimit(10**9)

R, C, K = mapint()
last_dp = [[0]*4 for _ in range(C)]
dic = [[0]*C for _ in range(R)]
for _ in range(K):
    r, c, v = mapint()
    dic[r-1][c-1] = v

for r in range(R):
    dp = [[0]*4 for _ in range(C)]
    for c in range(C):
        v = dic[r][c]
        for i in range(4):
            if c!=0:
                dp[c][i] = dp[c-1][i]
            if r!=0:
                dp[c][0] = max(dp[c][0], last_dp[c][i])
        if v!=0:
            for i in range(2, -1, -1):
                dp[c][i+1] = max(dp[c][i+1], dp[c][i]+v)
    last_dp = dp

print((max(dp[C-1])))
# Original solution
R, C, K = list(map(int, input().split()))
X = [list(map(int, input().split())) for _ in range(K)]

items = [[0] * (C + 1) for _ in range(R + 1)]
for r, c, v in X:
    items[r][c] = v

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):
        # k=0, horizontal and vertical transitions are allowed
        dp[i][j][0] = max(dp[i][j - 1][0], dp[i - 1][j][0], dp[i - 1][j][1],
                          dp[i - 1][j][2], dp[i - 1][j][3])

        # k=1~3, horizontal transition and picking up are allowed
        dp[i][j][3] = max(dp[i][j - 1][3], dp[i][j - 1][2] + items[i][j],
                          dp[i][j][2] + items[i][j])

        dp[i][j][2] = max(dp[i][j - 1][2], dp[i][j - 1][1] + items[i][j],
                          dp[i][j][1] + items[i][j])

        dp[i][j][1] = max(dp[i][j - 1][1], dp[i][j - 1][0] + items[i][j],
                          dp[i][j][0] + items[i][j])

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


# Optimized solution

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

items = [[0] * (C + 1) for _ in range(R + 1)]
for r, c, v in X:
    items[r][c] = v

dp = [[0] * 4 for _ in range(C + 1)]
for i in range(1, R + 1):
    # Vertical transition
    for j in range(1, C + 1):
        dp[j][0] = max(dp[j])
        for k in range(1, 4):
            dp[j][k] = 0

    # Horizontal or picking-up transition
    for j in range(1, C + 1):
        for k in reversed(list(range(4))):
            dp[j][k] = max(dp[j][k], dp[j - 1][k])
            if items[i][j] and k < 3:
                dp[j][k + 1] = max(dp[j][k + 1], dp[j][k] + items[i][j])

print((max(dp[-1])))
# Original solution
from sys import stdin
input = stdin.readline
(R,C,K) = list(map(int, input().split()))
rcv = [list(map(int, input().split())) for _ in range(K)]

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

for r,c,v in rcv:
    grids[r-1][c-1] = v

from collections import defaultdict
dp = defaultdict(int)

for r in range(R):
    for c in range(C):
        tmp = value = grids[r][c]
        for i in range(1,4):
            if c:
                tmp = max(tmp, dp[r,c-1,i])
                if i > 1:
                    tmp = max(tmp, dp[r,c-1,i-1] + value)
            if r and i == 1:
                tmp = max(tmp, dp[r-1,c,3] + value)
            dp[r,c,i] = tmp

print((dp[R-1,C-1,3]))

# Optimized solution
# from sys import stdin
# input = stdin.readline
(R,C,K) = list(map(int, input().split()))
rcv = [list(map(int, input().split())) for _ in range(K)]
 
grids = [[0]*C for _ in range(R)]
 
for r,c,v in rcv:
    grids[r-1][c-1] = v
 
dp = [0] * C

for r in range(R):
#     print(dp)
    ndp = [0] * C
    elm = [0] * 4
    for c in range(C):
        elm[0] = max(elm[0], dp[c])
        value = grids[r][c]
        if value:
            nelm = [0] * 4
            nelm[0] = elm[0]
#             print(f'{value=}')
#             print(f'{ elm=}')
#             print(f'{nelm=}')
            for i in range(3)[::-1]:
                nelm[i + 1] = max(elm[i + 1], elm[i] + value)
#             print(f'{value=}')
#             print(f'{ elm=}')
#             print(f'{nelm=}')
            elm = nelm
        ndp[c] = max(elm)
    dp = ndp
 

print((dp[-1]))
# Original solution
import sys
from collections import deque
import bisect
import copy
import heapq
import itertools
import math
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return list(map(int, input().split()))
def read_index(): return [int(x) - 1 for x in input().split()]
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v
 
    def __str__(self):
        return str(self.v)
 
    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n) 


def main():
    R, C, K = read_values()
    V2 = [0] * (R * C)
    for _ in range(K):
        r, c, v = read_values()
        r -= 1
        c -= 1
        V2[r * C + c] = v
    
    dp = [[V(max, 0) for _ in range(4)] for _ in range(R * C)]
    for i in range(R * C):
        r = i // C
        c = i % C
        if c + 1 < C:
            # not take
            for k in range(4):
                dp[i + 1][k].ud(dp[i][k].v)

            # take 
            for k in range(3):
                dp[i + 1][k + 1].ud(dp[i][k].v + V2[i])

        # next r
        if r + 1 < R:
            for k in range(3):
                dp[i + C][0].ud(dp[i][k].v + V2[i])
            dp[i + C][0].ud(dp[i][3].v)

    print((max(k.v + (V2[-1] if i  < 3 else 0) for i, k in enumerate(dp[-1]))))


if __name__ == "__main__":
    main()



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

def read_values(): return list(map(int, input().split()))
def read_index(): return [int(x) - 1 for x in input().split()]
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def main():
    R, C, K = read_values()
    V = [0] * (R * C)
    for _ in range(K):
        r, c, v = read_values()
        r -= 1
        c -= 1
        V[r * C + c] = v
    
    dp = [0 for _ in range(R * C * 4)]
    for i in range(R * C):
        r = i // C
        c = i % C
        if c + 1 < C:
            # not take
            for k in range(4):
                dp[4 * (i + 1) + k] = max(dp[4 * (i + 1) + k], dp[4 * i + k])

            # take 
            for k in range(3):
                dp[4 * (i + 1) + k + 1] = max(dp[4 * (i + 1) + k + 1], dp[4 * i + k] + V[i])

        # next r
        if r + 1 < R:
            for k in range(4):
                dp[4 * (i + C)] = max(dp[4 * (i + C)], dp[4 * i + k] + (V[i] if k < 3 else 0))

    res = 0
    for k in range(4):
        res = max(res, dp[4 * (R * C - 1) + k] + (V[-1] if k < 3 else 0))

    print(res)


if __name__ == "__main__":
    main()
# Original solution
def main():
    import sys
    my_input = sys.stdin.readline
    H, W, K = list(map(int, my_input().split()))
    V = [[0] * W for _ in range(H)]
    for i in range(K):
        h, w, v = list(map(int, my_input().split()))
        h, w = h - 1, w - 1
        V[h][w] = v

    # dp[h][w][x] := h行w列にいて、h行からx個アイテムを拾っている時の価値の総和の最大値
    dp = [[[0] * 4 for j in range(W + 1)] for i in range(H + 1)]
    for h in range(1, H + 1):
        for w in range(1, W + 1):
            for k in range(1, 4):
                dp[h][w][k] = max(
                    dp[h][w][k],
                    dp[h - 1][w][-1],
                    dp[h - 1][w][-1] + V[h - 1][w - 1],
                    dp[h][w - 1][k],
                    dp[h][w - 1][k - 1] + V[h - 1][w - 1])

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


if __name__ == "__main__":
    main()


# Optimized solution
def main():
    import sys
    my_input = sys.stdin.readline
    H, W, K = list(map(int, my_input().split()))
    V = [[0] * W for _ in range(H)]
    for i in range(K):
        h, w, v = list(map(int, my_input().split()))
        h, w = h - 1, w - 1
        V[h][w] = v

    # dp1 ~ 4[h][w][x] := h行w列にいて、h行からn個アイテムを拾っている時の価値の総和の最大値
    dp0 = [[0] * (W + 1) for _ in range(H + 1)]
    dp1 = [[0] * (W + 1) for _ in range(H + 1)]
    dp2 = [[0] * (W + 1) for _ in range(H + 1)]
    dp3 = [[0] * (W + 1) for _ in range(H + 1)]

    for h in range(1, H + 1):
        for w in range(1, W + 1):
            dp1[h][w] = max(
                dp1[h][w],
                dp3[h - 1][w] + V[h - 1][w - 1],
                dp1[h][w - 1],
                dp0[h][w - 1] + V[h - 1][w - 1]
            )

            dp2[h][w] = max(
                dp2[h][w],
                dp3[h - 1][w] + V[h - 1][w - 1],
                dp2[h][w - 1],
                dp1[h][w - 1] + V[h - 1][w - 1]
            )

            dp3[h][w] = max(
                dp3[h][w],
                dp3[h - 1][w] + V[h - 1][w - 1],
                dp3[h][w - 1],
                dp2[h][w - 1] + V[h - 1][w - 1]
            )

    print((dp3[-1][-1]))


if __name__ == "__main__":
    main()