Problem:
 Score : 500 points    Problem Statement There are K items placed on a grid of squares with R rows and C columns. Let (i, j) denote the square at the i -th row ( 1 \leq i \leq R ) and the j -th column ( 1 \leq j \leq C ). The i -th item is at (r_i, c_i) and has the value v_i .  Takahashi will begin at (1, 1) , the start, and get to (R, C) , the goal. When he is at (i, j) , he can move to (i + 1, j) or (i, j + 1) (but cannot move to a non-existent square).  He can pick up items on the squares he visits, including the start and the goal, but at most three for each row. It is allowed to ignore the item on a square he visits.  Find the maximum possible sum of the values of items he picks up.      Constraints  1 \leq R, C \leq 3000  1 \leq K \leq \min(2 \times 10^5, R \times C)  1 \leq r_i \leq R  1 \leq c_i \leq C  (r_i, c_i) \neq (r_j, c_j) (i \neq j)  1 \leq v_i \leq 10^9  All values in input are integers.         Input Input is given from Standard Input in the following format:  R  C  K  r_1  c_1  v_1  r_2  c_2  v_2  :  r_K  c_K  v_K       Output Print the maximum possible sum of the values of items Takahashi picks up.        Sample Input 1 2 2 3
1 1 3
2 1 4
1 2 5      Sample Output 1 8  He has two ways to get to the goal:   Visit (1, 1) , (1, 2) , and (2, 2) , in this order. In this case, the total value of the items he can pick up is 3 + 5 = 8 .  Visit (1, 1) , (2, 1) , and (2, 2) , in this order. In this case, the total value of the items he can pick up is 3 + 4 = 7 .   Thus, the maximum possible sum of the values of items he picks up is 8 .       Sample Input 2 2 5 5
1 1 3
2 4 20
1 2 1
1 3 4
1 4 2      Sample Output 2 29  We have four items in the 1 -st row. The optimal choices are as follows:   Visit (1, 1)  (1, 2) , (1, 3) , (1, 4) , (2, 4) , and (2, 5) , in this order, and pick up all items except the one on (1, 2) . Then, the total value of the items he picks up will be 3 + 4 + 2 + 20 = 29 .        Sample Input 3 4 5 10
2 5 12
1 5 12
2 3 15
1 2 20
1 1 28
2 4 26
3 2 27
4 5 21
3 5 10
1 3 10      Sample Output 3 142

Solution (Python):
r, c, k = map(int, input().split())

dp = [[[0,0,0,0] for _j in range(c+1)] for _i in range(2)]
bord = [[0]*(c+1) for _i in range(r)]

for _i in range(k):
    _r, _c, _v = map(int, input().split())
    bord[_r-1][_c-1] = _v
            
for i in range(r):
    for j in range(c):
        dp[1][j][0] = max(dp[0][j])
        dp[1][j][1] = max(
            dp[1][j][0] + bord[i][j],
            dp[1][j-1][1],
            dp[1][j-1][0]+bord[i][j]
        )

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

    dp[0] = dp[1][::]

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

Solution (Python):
mycode = r'''


ctypedef long long LL

from libc.stdio cimport scanf
from libcpp.vector cimport vector
ctypedef vector[LL] vec
ctypedef vector[vec] vec_vec

cdef LL R,C,K,i,j,k

scanf("%lld %lld %lld",&R,&C,&K)

cdef vec_vec dp,ndp,item

dp = vec_vec(C,vec(3,0))
ndp = vec_vec(C,vec(3,0))
item = vec_vec(R,vec(C,0))


cdef LL r,c,v

for i in range(K):
    scanf("%lld %lld %lld",&r,&c,&v)
    item[r-1][c-1] = v

dp[C-1][0] = item[R-1][C-1]
dp[C-1][1] = item[R-1][C-1]
dp[C-1][2] = item[R-1][C-1]

for j in range(C-2,-1,-1):
    dp[j][0]=max(dp[j+1][1]+item[R-1][j],dp[j+1][0])
    dp[j][1]=max(dp[j+1][2]+item[R-1][j],dp[j+1][1])
    dp[j][2]=max(item[R-1][j],dp[j+1][2])

for i in range(R-2,-1,-1):
    ndp = vec_vec(C,vec(3,0))
    ndp[C-1][0]=dp[C-1][0]+item[i][C-1]
    ndp[C-1][1]=dp[C-1][0]+item[i][C-1]
    ndp[C-1][2]=dp[C-1][0]+item[i][C-1]
    for j in range(C-2,-1,-1):
        ndp[j][0]=max(max(dp[j][0],ndp[j+1][1])+item[i][j],ndp[j+1][0])
        ndp[j][1]=max(max(dp[j][0],ndp[j+1][2])+item[i][j],ndp[j+1][1])
        ndp[j][2]=max(dp[j][0]+item[i][j],ndp[j+1][2])
    dp=ndp

print(dp[0][0])

'''

import sys
import os
if sys.argv[-1] == 'ONLINE_JUDGE':  
    with open('mycode.pyx', 'w') as f:
        f.write(mycode)
    os.system('cythonize -i -3 -b mycode.pyx')

import mycode

Solution (Python):
mycode = r'''


ctypedef long long LL

from libc.stdio cimport scanf
from libcpp.vector cimport vector
ctypedef vector[LL] vec

cdef LL R,C,K,i,j,k

scanf("%lld %lld %lld",&R,&C,&K)

cdef vector[vector[LL]] dp = [[0 for j in range(3)] for i in range(C)]
cdef vector[vector[LL]] ndp = [[0 for j in range(3)] for i in range(C)]
cdef vector[vector[LL]] item = [[0 for j in range(C)] for i in range(R)]
cdef LL r,c,v

for i in range(K):
    scanf("%lld %lld %lld",&r,&c,&v)
    item[r-1][c-1] = v

dp[C-1][0] = item[R-1][C-1]
dp[C-1][1] = item[R-1][C-1]
dp[C-1][2] = item[R-1][C-1]

for j in range(C-2,-1,-1):
    dp[j][0]=max(dp[j+1][1]+item[R-1][j],dp[j+1][0])
    dp[j][1]=max(dp[j+1][2]+item[R-1][j],dp[j+1][1])
    dp[j][2]=max(item[R-1][j],dp[j+1][2])

for i in range(R-2,-1,-1):
    ndp = [[0 for j in range(3)] for i in range(C)]
    ndp[C-1][0]=dp[C-1][0]+item[i][C-1]
    ndp[C-1][1]=dp[C-1][0]+item[i][C-1]
    ndp[C-1][2]=dp[C-1][0]+item[i][C-1]
    for j in range(C-2,-1,-1):
        ndp[j][0]=max(max(dp[j][0],ndp[j+1][1])+item[i][j],ndp[j+1][0])
        ndp[j][1]=max(max(dp[j][0],ndp[j+1][2])+item[i][j],ndp[j+1][1])
        ndp[j][2]=max(dp[j][0]+item[i][j],ndp[j+1][2])
    dp=ndp

print(dp[0][0])

'''

import sys
import os
if sys.argv[-1] == 'ONLINE_JUDGE':  
    with open('mycode.pyx', 'w') as f:
        f.write(mycode)
    os.system('cythonize -i -3 -b mycode.pyx')

import mycode

Solution (Python):
import sys
import math
import copy
import random
import itertools
from heapq import heappush, heappop, heapify
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter
sys.setrecursionlimit(1000000)


input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = 10 ** 21
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)

def solve(n=None, s1=None, s2=None):
    r, c, k = getList()
    value = [[0] * (c + 1) for i in range(r)]

    for i in range(k):
        cr, cc, cv = getZList()
        cv += 1
        value[cr][cc + 1] = cv

    dp = [[[0] * (c + 1) for i in range(r)] for j in range(4)]
    
    
    for y in range(r):
        for x in range(1, c+1):
            curv = value[y][x]
            if y > 0:
                dp[0][y][x] = max(
                    dp[0][y-1][x],
                    dp[1][y-1][x],
                    dp[2][y-1][x],
                    dp[3][y-1][x]
                )
                dp[1][y][x] = max(
                    dp[0][y - 1][x] + curv,
                    dp[1][y - 1][x] + curv,
                    dp[2][y - 1][x] + curv,
                    dp[3][y - 1][x] + curv
                )
            if curv == 0:
                for z in range(4):
                    dp[z][y][x] = max(dp[z][y][x], dp[z][y][x-1])

            else:
                dp[0][y][x] = max(dp[0][y][x], dp[0][y][x-1])
                dp[1][y][x] = max(dp[1][y][x], dp[1][y][x-1], dp[0][y][x-1] + curv)
                dp[2][y][x] = max(dp[2][y][x], dp[2][y][x-1], dp[1][y][x - 1] + curv)
                dp[3][y][x] = max(dp[3][y][x], dp[3][y][x-1], dp[2][y][x - 1] + curv)

    
    

    ans = 0
    for z in range(4):
        for y in range(r):
            for x in range(1, c+1):
                ans = max(ans, dp[z][y][x])

    print(ans)

def main():
    n = getN()
    for _ in range(n):
        solve()
    return


if __name__ == "__main__":
    
    solve()

Solution (Python):
R, C, K = map(int, input().split())
score = [[0]*C for i in range(R)]

for i in range(K):
  r, c, v = map(int, input().split())
  score[r-1][c-1]+=v
  
ans0 = [[0]*C for i in range(R)]
ans1 = [[0]*C for i in range(R)]
ans2 = [[0]*C for i in range(R)]
ans3 = [[0]*C for i in range(R)]

ans1[0][0]=score[0][0]
ans2[0][0]=score[0][0]
ans3[0][0]=score[0][0]

for i in range(R):
  for j in range(C):
    if i>0:
      ans0[i][j]=max(ans0[i][j],ans3[i-1][j])
      ans1[i][j]=max(ans1[i][j],ans3[i-1][j]+score[i][j])
      ans2[i][j]=max(ans2[i][j],ans3[i-1][j]+score[i][j])
      ans3[i][j]=max(ans3[i][j],ans3[i-1][j]+score[i][j])
    if j>0:
      ans0[i][j]=max(ans0[i][j],ans0[i][j-1])
      ans1[i][j]=max(ans1[i][j],ans0[i][j-1]+score[i][j],ans1[i][j-1])
      ans2[i][j]=max(ans2[i][j],ans1[i][j-1]+score[i][j],ans2[i][j-1])
      ans3[i][j]=max(ans3[i][j],ans2[i][j-1]+score[i][j],ans3[i][j-1])

print(ans3[R-1][C-1])

Solution (Python):
R, C, K = map(int, input().split())

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

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

for i in range(R):
    dp2 = [[0] * 4 for _ in range(C)]
    for j in range(C):
        if j != 0:
            dp2[j] = dp2[j-1][:]

        dp2[j][0] = max(dp2[j][0], max(dp[j]))

        for k in range(3, 0, -1):
            dp2[j][k] = max(dp2[j][k], dp2[j][k-1] + items[i][j])

    dp = dp2

print(max(dp[-1]))

Solution (Python):
R,C,K=map(int,input().split())
G=[[0]*(C+1) for i in range(R+1)]
for i in range(K):
    r,c,v=map(int,input().split())
    G[r][c]=v
dp=[[0]*(C+1) for i in range(R+1)]
for i in range(1,R+1):
    d1,d2,d3=0,0,0
    for j in range(1,C+1):
        v=G[i][j]
        if v!=0:
            if d2!=0:
                d3=max(d3,d2+v)
            if d1!=0:
                d2=max(d2,d1+v)
            d1=max(dp[i-1][j]+v,d1)
        else:
            d1=max(dp[i-1][j],d1)
        dp[i][j]=max(d1,d2,d3)
print(dp[R][C])

Solution (Python):
R,C,K = map(int, input().split())
a = [[0] * (C+1) for i in range(R+1)]
dp = [[[0] * (C+1) for i in range(R+1)] for j in range(4)]
for i in range(K):
  r,c,v = map(int, input().split())
  a[r-1][c-1] = v
  
for i in range(R):
  for j in range(C):
    for k in range(2,-1,-1):
      dp[k+1][i][j] = max(dp[k+1][i][j], dp[k][i][j] + a[i][j])
    for k in range(4):
      dp[0][i+1][j] = max(dp[0][i+1][j], dp[k][i][j])
      dp[k][i][j+1] = max(dp[k][i][j+1], dp[k][i][j])
ans = 0
for k in range(4):
  ans = max(ans, dp[k][R-1][C-1])
print(ans)

Solution (Python):
r,c,kk = map(int, input().split())

a = [[0 for j in range(c)] for i in range(r)]
dp1 = [[0 for j in range(c+1)] for i in range(r+1)]
dp2 = [[0 for j in range(c+1)] for i in range(r+1)]
dp3 = [[0 for j in range(c+1)] for i in range(r+1)]
dp4 = [[0 for j in range(c+1)] for i in range(r+1)]

for i in range(kk):
  b,cc,d = map(int, input().split())
  b -= 1
  cc -= 1
  a[b][cc] = d

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

Solution (Python):
import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8
import sys

R, C, K = map(int, input().split())
rcvs = [list(map(int, input().split())) for _ in range(K)]
rcvs = np.array(rcvs, dtype=np.int64)

@njit
def main(rcvs):
    rewards = np.zeros((R, C), dtype=np.int64)
    
    for i in range(len(rcvs)):
        rewards[rcvs[i][0]-1][rcvs[i][1]-1] = rcvs[i][2]
    
    dp = np.zeros((R+1, C+1, 4), dtype=np.int64)
    
    for i in range(R):
        for j in range(C):
            reward = rewards[i][j]
            dp[i+1][j+1][0] = max(dp[i][j+1])
            dp[i+1][j+1][1] = dp[i+1][j+1][0] + reward
            
            for k in range(4): 
                dp[i+1][j+1][k] = max(dp[i+1][j][k], dp[i+1][j+1][k])
            if reward > 0:
                for k in range(3):
                    dp[i+1][j+1][k+1] = max(dp[i+1][j][k]+reward,dp[i+1][j+1][k+1])
    return max(dp[-1][-1])

print(main(rcvs))

"""
メモ
ndarrayの型宣言でtype指定できない
typeコマンドも機能しない
iteration使えない
グローバル変数使える
main(As)
"""

Solution (Python):
import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8
import sys

R, C, K = map(int, input().split())
rcvs = [list(map(int, input().split())) for _ in range(K)]
rcvs = np.array(rcvs, dtype=np.int64)

@njit(i8(i8[:,:]), cache=True)
def main(rcvs):
    rewards = np.zeros((R, C), dtype=np.int64)
    
    for i in range(len(rcvs)):
        rewards[rcvs[i][0]-1][rcvs[i][1]-1] = rcvs[i][2]
    
    dp = np.zeros((R+1, C+1, 4), dtype=np.int64)
    
    for i in range(R):
        for j in range(C):
            reward = rewards[i][j]
            dp[i+1][j+1][0] = max(dp[i][j+1])
            dp[i+1][j+1][1] = dp[i+1][j+1][0] + reward
            
            for k in range(4): 
                dp[i+1][j+1][k] = max(dp[i+1][j][k], dp[i+1][j+1][k])
            if reward > 0:
                for k in range(3):
                    dp[i+1][j+1][k+1] = max(dp[i+1][j][k]+reward,dp[i+1][j+1][k+1])
    return max(dp[-1][-1])

print(main(rcvs))

Solution (Python):
R,C,K=map(int,input().split())

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

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

dp=[[0 for _ in range(4)] for _ in range(C+1)]
for i in range(R):
    ndp=[[0 for _ in range(4)] for _ in range(C+1)]
    for j in range(C):
        ndp[j][0]=max(dp[j])

    for j in range(C):
        v=V[i][j]
        for n in range(1,4):
            ndp[j][n]=max(ndp[j-1][n-1]+v,dp[j][3]+v,ndp[j-1][n])

    dp=ndp

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

Solution (Python):
import numpy as np
from numba import njit, i8


@njit(i8(i8, i8, i8[:, :]), cache=True)
def solve(R, C, items):
    dp = np.zeros((R + 1, C + 1, 4), dtype=np.int64)
    for i in range(R):
        for j in range(C):
            for k in range(2, -1, -1):
                dp[i][j][k + 1] = max(dp[i][j][k + 1], dp[i][j][k] + items[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])
    return dp[R][C - 1][0]


R, C, K, *rcv = map(int, open(0).read().split())
items = np.zeros((R + 1, C + 1), dtype=np.int64)
for r, c, v in zip(*[iter(rcv)] * 3):
    items[r - 1][c - 1] = v
print(solve(R, C, items))

Solution (Python):
H, W, k = map(int, input().split())
"""
dp[k][i][j]
i行目、j番目まで来た時に、k個アイテムをとったときの価値の最大値
"""
fs = [[0]*(W+1) for i in range(H+1)]
dp = [[[-1]*(W+1) for i in range(H+1)] for j in range(4)]


for i in range(k):
    h, w, v = map(int, input().split())
    fs[h-1][w-1] += v


dp[0][0][0] = 0
dp[1][0][0] = fs[0][0]

for h in range(H):
    for w in range(W):
        for i in range(4):
            if i == 0:
                dp[i][h][w+1] = max(dp[0][h][w], dp[0][h][w+1])
            else:
                dp[i][h][w+1] = max(dp[i][h][w], dp[i][h][w+1], dp[i-1][h][w]+fs[h][w+1])
    for w in range(W):
        dp[0][h+1][w] = max(dp[0][h][w],dp[1][h][w],dp[2][h][w],dp[3][h][w],0)
        dp[1][h+1][w] = dp[0][h+1][w] + fs[h+1][w]

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

Solution (Python):
H, W, K = map(int, input().split())
Map = [[0] * (W + 1) for _ in range(H + 1)]
for _ in range(K):
    h, w, k = map(int, input().split())
    Map[h][w] = k

DP = [[[0] * (H + 1) for _ in range(W + 1)] for __ in range(4)]


for i in range(1, H + 1):
    for j in range(1, W + 1):
        x = Map[i][j]
        if Map:
            DP[0][j][i] = max(DP[0][j][i-1], DP[1][j][i-1], DP[2][j][i-1], DP[3][j][i-1], DP[0][j-1][i])
            DP[1][j][i] = max(DP[1][j - 1][i], DP[0][j-1][i] + x, DP[0][j][i-1] + x, DP[1][j][i-1] + x, DP[2][j][i-1] + x, DP[3][j][i-1] + x)
            DP[2][j][i] = max(DP[2][j - 1][i], DP[1][j-1][i] + x)
            DP[3][j][i] = max(DP[3][j - 1][i], DP[2][j-1][i] + x)

        else:
            DP[0][j][i] = max(DP[0][j][i-1], DP[1][j][i-1], DP[2][j][i-1], DP[3][j][i-1], DP[0][j-1][i])
            DP[1][j][i] = DP[1][j-1][i]
            DP[2][j][i] = DP[2][j-1][i]
            DP[3][j][i] = DP[3][j-1][i]

print(max(DP[0][W][H], DP[1][W][H], DP[2][W][H], DP[3][W][H]))

Solution (Python):
R,C,K = map(int,input().split())
items = [[0]*(C+1) for _ in range(R+1)]
for i in range(K):
    r,c,v = map(int,input().split())
    items[r][c] = v

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

for y in range(R+1):
    for x in range(C+1):
        for i in range(4):
            position = dp[i][y][x]
            if y+1 <= R:
                dp[0][y+1][x] = max(dp[0][y+1][x], position)
                dp[1][y+1][x] = max(dp[1][y+1][x], position+items[y+1][x])
            if x+1 <= C:
                dp[i][y][x+1] = max(dp[i][y][x+1], position)
                if i < 3:
                    dp[i+1][y][x+1] = max(dp[i+1][y][x+1], position+items[y][x+1])

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

Solution (Python):
r,c,k = map(int, input().split())
rckl = [ [0]*c for _ in range(r) ]

for _ in range(k):
    r_,c_,v_ = map(int, input().split())
    rckl[r_-1][c_-1] = v_

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


dp1[0][0] = rckl[0][0]

for i in range(r):
    for j in range(c):
        if j+1 < c: 
            dp0[i][j+1] = max(dp0[i][j], dp0[i][j+1]) 
            dp1[i][j+1] = max(dp1[i][j], dp1[i][j+1]) 
            dp2[i][j+1] = max(dp2[i][j], dp2[i][j+1]) 
            dp3[i][j+1] = max(dp3[i][j], dp3[i][j+1]) 
            if rckl[i][j+1] > 0:
                v = rckl[i][j+1] 
                dp1[i][j+1] = max(dp1[i][j+1], dp0[i][j] + v)
                dp2[i][j+1] = max(dp2[i][j+1], dp1[i][j] + v)
                dp3[i][j+1] = max(dp3[i][j+1], dp2[i][j] + v)

        if i+1 < r: 
            dp0[i+1][j] = max(dp0[i][j], dp1[i][j], dp2[i][j], dp3[i][j], dp0[i+1][j]) 
            if rckl[i+1][j] > 0:
                v = rckl[i+1][j] 
                dp1[i+1][j] = max(dp1[i+1][j], dp0[i][j]+v, dp1[i][j]+v, dp2[i][j]+v, dp3[i][j]+v)


ans = max(dp0[-1][-1], dp1[-1][-1], dp2[-1][-1], dp3[-1][-1])
print(ans)

Solution (Python):
R,C,K=map(int,input().split())

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

DP=[[0,0,0,0] for _ in range(C+1) ]

for y in range(1,R+1):
    
    for x in range(1,C+1):
        DP[x][0]=max(DP[x])
        DP[x][1]=DP[x][0]+Value[y][x]
        DP[x][2]=DP[x][3]=0

    
    for x in range(1,C+1):
        for k in range(0,3+1):
            DP[x][k]=max(DP[x][k],DP[x-1][k])

        for k in range(1,3+1):
            DP[x][k]=max(DP[x][k],DP[x-1][k-1]+Value[y][x])

print(max(DP[-1]))

Solution (Python):
import numpy as np
from numba import njit

rr,cc,kk=map(int,input().split())
goods=np.array([list(map(int,input().split())) for _ in range(kk)])
gg=np.zeros((rr,cc))
for cr,ccc,ck in goods:
    gg[cr-1][ccc-1]=ck

@njit
def calc(r,c,g):
    dp=-1*np.ones((r+1,c+1,4))
    maxlst=np.zeros((r+1,c+1))

    dp[:,0,0]=0
    dp[0,:,0]=0
    
    for i in range(r):
        for j in range(c):
            tmp=0
            for k in range(3):
                if g[i][j]>0 and dp[i+1][j][k]>=0:
                    dp[i+1][j+1][k+1]=max(dp[i+1][j][k+1],dp[i+1][j][k]+g[i][j])
                else:
                    dp[i+1][j+1][k+1]=dp[i+1][j][k+1]
                tmp=max(tmp,dp[i+1][j+1][k+1])
            
            dp[i+1][j+1][0]=max(maxlst[i][j+1],dp[i+1][j][0])
            tmp=max(tmp,dp[i+1][j+1][0])
            
            if g[i][j]>0 and dp[i+1][j+1][0]>=0:
                dp[i+1][j+1][1]=max(dp[i+1][j+1][1],dp[i+1][j+1][0]+g[i][j])
                tmp=max(tmp,dp[i+1][j+1][1])
            
            maxlst[i+1][j+1]=tmp
    
    return maxlst[r][c]
            
print(int(calc(rr,cc,gg)))

Solution (Python):
r,c,k = list(map(int, input().split()))
import copy
dp=[[[0]*4 for _ in range(c)] for _ in range(2)]


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

for _ in range(k):
  x,y,v = list(map(int, input().split()))
  x-=1
  y-=1
  F[x][y] = v
  
for nn in range(r):
  for j in range(c):
    i = 1
    val = F[nn][j]
  
      
    mxv = max(dp[i-1][j][0], dp[i-1][j][1], dp[i-1][j][2], dp[i-1][j][3])

    dp[i][j][3] = max(dp[i][j-1][3], dp[i][j-1][2] + val)
    dp[i][j][2] = max(dp[i][j-1][2], dp[i][j-1][1] + val)
    dp[i][j][1] = max(dp[i][j-1][1], dp[i][j-1][0] + val, mxv + val)
    dp[i][j][0] = mxv

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

best = 0


for k in range(4):
  best = max(best, dp[0][c-1][k])
    
print(best)

Solution (Python):
h,w,k = map(int, input().split())
item = [[0 for _ in range(w)] for _ in range(h)]
for i in range(k):
    y,x,v = list(map(int,input().split()))
    item[y-1][x-1]=v

dp = [[[0 for _ in range(w+1)] for _ in range(h+1)] for _ in range(4)]

for y in range(h):
    for x in range(w):
        for i in range(4):
            dp[0][y+1][x]=max(dp[0][y+1][x],dp[i][y][x])
            dp[i][y][x+1]=max(dp[i][y][x+1],dp[i][y][x])
        if item[y][x]>0:
            for i in range(3):
                dp[0][y+1][x]  =max(dp[0][y+1][x],  dp[i][y][x]+item[y][x])
                dp[i+1][y][x+1]=max(dp[i+1][y][x+1],dp[i][y][x]+item[y][x])
ans=dp[0][-1][-2]
print(ans)

Solution (Python):
h,w,k = map(int, input().split())
item = [[0 for _ in range(w)] for _ in range(h)]
for i in range(k):
    y,x,v = list(map(int,input().split()))
    item[y-1][x-1]=v

dp = [[[0 for _ in range(w)] for _ in range(h)] for _ in range(4)]

for y in range(h):
    for x in range(w):
        for i in range(4):
            if y<h-1:
                dp[0][y+1][x]=max(dp[0][y+1][x],dp[i][y][x])
            if x<w-1:
                dp[i][y][x+1]=max(dp[i][y][x+1],dp[i][y][x])

        if item[y][x]>0:
            for i in range(3):
                if y<h-1:
                    dp[0][y+1][x]=max(dp[0][y+1][x],dp[i][y][x] + item[y][x])
                if x<w-1:
                    dp[i+1][y][x+1]=max(dp[i+1][y][x+1],dp[i][y][x] + item[y][x])

ans=[dp[0][-1][-1] + item[-1][-1],
     dp[1][-1][-1] + item[-1][-1],
     dp[2][-1][-1] + item[-1][-1],
     dp[3][-1][-1]]
print(max(ans))

Solution (Python):
r,c,k = list(map(int, input().split()))
import copy
dp=[[[0]*4 for _ in range(c)] for _ in range(2)]


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

for _ in range(k):
  x,y,v = list(map(int, input().split()))
  x-=1
  y-=1
  F[x][y] = v
  
for nn in range(r):
  for j in range(c):
    i = 1
    val = F[nn][j]
  
      
    mxv = max(dp[i-1][j][0], dp[i-1][j][1], dp[i-1][j][2], dp[i-1][j][3],0)

    dp[i][j][3] = max(dp[i][j-1][3], dp[i][j-1][2] + val)
    dp[i][j][2] = max(dp[i][j-1][2], dp[i][j-1][1] + val)
    dp[i][j][1] = max(dp[i][j-1][1], dp[i][j-1][0] + val, mxv + val)
    dp[i][j][0] = mxv

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

best = 0


for k in range(4):
  best = max(best, dp[0][c-1][k])
    
print(best)

Solution (Python):
"""
dp[i][j][k] => i行目、j列のマスまで見る。k個取る時の最高値。
"""
def main():
    import sys
    input = sys.stdin.readline
    R,C,K = map(int,input().split())
    items = [[0]*C for _ in range(R)]
    for _ in range(K):
        r,c,v = 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:
                
                
                dp[j][0] = max(dp[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()

Solution (Python):
H, W, K = map(int, input().split())
A = [[0] * W for _ in range(H)]
for i in range(K):
    y, x, v = map(int, input().split())
    A[y - 1][x - 1] = v
dp = [[0] * 4 for i in range(W)]
pre = []
dp[0][1] = A[0][0]
for i in range(H):
    for j in range(W):
        if i:
            dp[j][0] = max(dp[j][0], max(pre[j]))
            dp[j][1] = max(dp[j][1], max(pre[j]) + A[i][j])
        for k in range(4):
            if j:
                if 0 < k:
                    dp[j][k] = max(dp[j][k], dp[j - 1][k - 1] + A[i][j])
                dp[j][k] = max(dp[j][k], dp[j - 1][k])
    pre = dp
ans = 0
for j in range(W):
    ans = max(ans, max(dp[j]))
print(ans)

Solution (Python):
H, W, K = map(int, input().split())
A = [[0] * W for _ in range(H)]
for i in range(K):
    y, x, v = map(int, input().split())
    A[y - 1][x - 1] = v
dp = [[0] * 4 for i in range(W)]
pre = []
dp[0][1] = A[0][0]
for i in range(H):
    for j in range(W):
        for k in range(4):
            if i:
                if k == 1:
                        dp[j][k] = max(dp[j][k], max(pre[j]) + A[i][j])
                if k == 0:
                        dp[j][k] = max(dp[j][k], max(pre[j]))
            if j:
                if 0 < k:
                    dp[j][k] = max(dp[j][k], dp[j - 1][k - 1] + A[i][j])
                dp[j][k] = max(dp[j][k], dp[j - 1][k])
    pre = dp
ans = 0
for j in range(W):
    ans = max(ans, max(dp[j]))
print(ans)

Solution (Python):
R,C,K = map(int, input().split())

maze = [[0 for _ in range(C)] for _ in range(R)]
dp = [[[0 for _ in range(C+1)] for _ in range(R+1)] for _ in range(4)]
for i in range(K):
    r,c,v = map(int, input().split())
    r -=1
    c -= 1
    maze[r][c] = v

for i in range(R):
    for j in range(C):
        
        for k in range(2, -1, -1):
            dp[k+1][i][j] = max(dp[k+1][i][j], dp[k][i][j] + maze[i][j])

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

ans = 0

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

print(ans)

Solution (Python):
R,C,K = map(int, input().split())
a = [[0] * (C+1) for i in range(R+1)]
dp = [[[0] * (C+1) for i in range(R+1)] for j in range(4)]

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

Solution (Python):
import sys,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
rep=range;R=range
def Golf():n,*t=map(int,open(0).read().split())
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def MI():return map(int,input().split())
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def RA():return map(int,open(0).read().split())
def RLI(n=8,a=1,b=10):return [random.randint(a,b)for i in range(n)]
def RI(a=1,b=10):return random.randint(a,b)
def Rtest(T):
    case,err=0,0
    for i in range(T):
        inp=INP()
        a1,ls=naive(*inp)
        a2=solve(*inp)
        if a1!=a2:
            print((a1,a2),inp)
            err+=1
        case+=1
    print('Tested',case,'case with',err,'errors')
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'
    
    mp=[boundary]*(w+2);found={}
    for i in R(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def accum(ls):
    rt=[0]
    for i in ls:rt+=[rt[-1]+i]
    return rt
def bit_combination(n,base=2):
    rt=[]
    for tb in R(base**n):s=[tb//(base**bt)%base for bt in R(n)];rt+=[s]
    return rt
def gcd(x,y):
    if y==0:return x
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def YN(x):print(['NO','YES'][x])
def Yn(x):print(['No','Yes'][x])
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

mo=10**9+7
inf=float('inf')
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
l_alp=string.ascii_lowercase

read=sys.stdin.buffer.read;readline=sys.stdin.buffer.readline;input=lambda:sys.stdin.readline().rstrip()


show_flg=False
show_flg=True

ans=0

h,w,k=LI()
v=[[0]*(w+1) for i in range(h+1)]
for i in rep(k):
    a,b,x=LI()
    v[a][b]=x

dp=[[[0]*(w+1) for i in range(h+1)] for i in range(4)]

for i in range(1,h+1):
    for j in range(1,w+1):
        up_max=max(dp[x][i-1][j]for x in range(4))
        dp[0][i][j]=up_max
        if v[i][j]!=0:
            dp[1][i][j]=max(dp[1][i][j],up_max+v[i][j])
        dp[0][i][j]=max(dp[0][i][j],dp[0][i][j-1])
        for x in range(1,4)[::-1]:
            dp[x][i][j]=max(dp[x][i][j],dp[x][i][j-1],dp[x-1][i][j-1]+v[i][j])
            

ans=max([dp[x][h][w]for x in range(4)])
print(ans)

Solution (Python):
R,C,K = map(int, input().split())

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


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

for i in range(K):
    r, c, v = map(int, input().split())
    d[r-1][c-1] = v
for i in range(R):
    for j in range(C):
        
        for k in range(2, -1, -1):
            
            dp[k+1][i][j] = max(dp[k+1][i][j], dp[k][i][j] + d[i][j])
        for k in range(4):
            dp[0][i+1][j] = max(dp[0][i+1][j], dp[k][i][j])
            dp[k][i][j+1] = max(dp[k][i][j+1], dp[k][i][j])
ans = 0

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

Solution (Python):
R,C,K = map(int, input().split())

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

for i in range(K):
    r, c, v = map(int, input().split())
    d[r-1][c-1] = v
for i in range(R):
    for j in range(C):
        
        for k in range(2, -1, -1):
            
            dp[k+1][i][j] = max(dp[k+1][i][j], dp[k][i][j] + d[i][j])
        for k in range(4):
            dp[0][i+1][j] = max(dp[0][i+1][j], dp[k][i][j])
            dp[k][i][j+1] = max(dp[k][i][j+1], dp[k][i][j])
ans = 0

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