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-----
2 2 3
1 1 3
2 1 4
1 2 5

-----Sample Output-----
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.

Difficulty: interview

Starter code:

Solutions:
import numpy as np
from numba import njit
R,C,K=list(map(int,input().split()))
vl=np.zeros((R,C), np.int64)
for _ in range(K):
  r,c,v=list(map(int,input().split()))
  vl[r-1][c-1]=v
@njit
def main():
  dp=np.zeros((R+1,C+1,4), np.int64)
  for i in range(1,R+1):
    for j in range(1,C+1):
      for k in range(4):
        dp[i][j][k]=max(dp[i][j-1][k],dp[i-1][j][3])
      for k in range(3,0,-1):
        dp[i][j][k]=max(dp[i][j][k],dp[i][j][k-1]+vl[i-1][j-1])
  return dp[R][C][3]
print((main()))



import math
from numba import jit
import numpy as np

@jit
def solve():
    
    r,c,k = map(int,input().split())

    value = np.zeros((r,c), dtype=np.int64)
    for i in range(k):
        r_t,c_t,v_t = map(int,input().split())
        value[r_t-1][c_t-1] = v_t

    dp = np.zeros((r,c,4), dtype=np.int64)
    dp[0][0][0] = 0

    for i in range(r):
        for j in range(c):
            for m in range(4):
                if i + 1 < r:
                    dp[i+1][j][0] = max(dp[i+1][j][0],dp[i][j][m])
                if j + 1 < c:
                    dp[i][j+1][m] = max(dp[i][j+1][m],dp[i][j][m])
                if value[i][j] != 0 and m < 3:
                    if i + 1 < r:
                        dp[i+1][j][0] = max(dp[i+1][j][0],dp[i][j][m]+value[i][j])
                    if j + 1 < c:
                        dp[i][j+1][m+1] = max(dp[i][j+1][m+1],dp[i][j][m]+value[i][j])

    for m in range(2,-1,-1):
        dp[r-1][c-1][m+1] = max(dp[r-1][c-1][m+1],dp[r-1][c-1][m]+value[r-1][c-1])
    return max(dp[r-1][c-1])

print(solve())

import numba
from numba import jit
import numpy as np
 
#(i,j)→(i+1,j)のように動くときはアイテムを入手できる回数がリセットされる
#dp[列][今、何個アイテムを取ったか]でdpテーブルを作る
@jit
def main(r, c):
  dp = np.zeros((c+1, 4), np.int64)
  for i in range(r):
    new_dp = np.zeros((c+1, 4), np.int64)
    for j in range(4):
      new_dp[:,0] = np.maximum(new_dp[:,0], dp[:,j])
    dp = new_dp
    for k in range(c):
      for l in range(2, -1, -1):
        dp[k,l+1] = max(dp[k,l+1], dp[k,l]+item_map[i,k])
      for m in range(1,4):
        dp[k+1,m] = max(dp[k+1,m], dp[k,m])
  return max(dp[c-1,:])
 
R, C, K = map(int, input().split())
item_lis = list(list(map(int, input().split())) for i in range(K))
item_map = np.zeros((R, C), np.int64)
for i,j,k in item_lis:
  item_map[i-1,j-1] = k
 
print(main(R, C))

import sys
import numpy as np
from collections import defaultdict
from numba import njit
def input(): return sys.stdin.readline().rstrip()

@njit
def koushin(dp,item):
    dptmp1 = np.copy(dp)
    dptmp2 = np.copy(dp)
    dptmp3 = np.copy(dp)
    for i in range(len(item)):
        dptmp3[item[i][0]:] = np.fmax(dptmp3[item[i][0]:], dptmp2[item[i][0]]+item[i][1])
        dptmp2[item[i][0]:] = np.fmax(dptmp2[item[i][0]:], dptmp1[item[i][0]]+item[i][1])
        dptmp1[item[i][0]:] = np.fmax(dptmp1[item[i][0]:], dp[item[i][0]]+item[i][1])
    return dptmp3

def main():
    R, C, K = map(int, input().split())
    items = defaultdict(list)
    for _ in range(K):
        r, c, v = map(int, input().split())
        items[r-1].append([c-1, v])
    dp = np.zeros(C, dtype=int)
    for RR in range(R):
        if items[RR]==[]:
          continue
        items[RR].sort(key=lambda x: x[0])
        dp=koushin(dp,np.array(items[RR],dtype=int))
    print(dp[-1])


def __starting_point():
    main()
__starting_point()

import numpy as np
from numba import njit

R, C, K = map(int, input().split())
item = np.zeros((R, C), np.int_)
for _ in range(K):
    r, c, v = map(int, input().split())
    item[r-1,c-1] = v

@njit
def solve(R, C, K, item):
    DP = np.zeros((R, C, 4), np.int_)

    DP[0][0][1] = item[0][0]

    for i in range(R):
        for j in range(C):
            for k in range(4):
                if i > 0:  # 前の行から
                    DP[i,j,0] = max(DP[i,j,0], max(DP[i-1,j]))  # 取らない
                    DP[i,j,1] = max(DP[i,j,1], max(DP[i-1,j])+item[i,j])  # 取る

                if j > 0:  # 前の列から
                    DP[i,j,k] = max(DP[i,j,k], DP[i,j-1,k])  # 取らない
                    if k >= 1:
                        DP[i,j,k] = max(DP[i,j,k], DP[i,j-1,k-1]+item[i,j])  # 取る

    print(max(DP[R-1,C-1]))

solve(R, C, K, item)

import numba
from numba import jit
import numpy as np
  
@jit
def main(r, c):
  dp = np.zeros((c+1, 4), np.int64)
  for i in range(r):
    new_dp = np.zeros((c+1, 4), np.int64)
    for j in range(4):
      new_dp[:,0] = np.maximum(new_dp[:,0], dp[:,j])
    dp = new_dp
    for k in range(c):
      for l in range(2, -1, -1):
        dp[k,l+1] = max(dp[k,l+1], dp[k,l]+item_map[i,k])
      for m in range(1,4):
        dp[k+1,m] = max(dp[k+1,m], dp[k,m])
  return max(dp[c-1,:])


R, C, K = map(int, input().split())
item_lis = list(list(map(int, input().split())) for i in range(K))
item_map = np.zeros((R, C), np.int64)
for i,j,k in item_lis:
  item_map[i-1,j-1] = k

print(main(R, C))

import sys
import numpy as np
from numba import jit, void, i8
input = sys.stdin.readline

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

    L_INF = int(1e17)
    dp = np.full((R+1, C+1, 4), -L_INF, dtype=np.int64)
    cell = np.full((R+1, C+1), 0, dtype=np.int64)

    for i in range(K):
        x, y, c = list(map(int, input().split()))
        cell[x-1][y-1] = c

    f(dp, cell, R, C)

    print((dp[R][C][3]))

@jit(void(i8[:,:,:],i8[:,:],i8,i8))
def f(dp, cell, R, C):
    dp[0][1][0] = dp[1][0][0] = 0
    for i in range(1, R + 1):
        for j in range(1, C + 1):
            for k in range(4):
                if k > 0:
                    dp[i][j][k] = max(dp[i][j][k], dp[i][j][k-1])
                dp[i][j][k] = max(dp[i][j][k], dp[i][j-1][k])
                if k > 0:
                    dp[i][j][k] = max(dp[i][j][k], dp[i][j-1][k-1] + cell[i-1][j-1])
                if k == 1:
                    dp[i][j][k] = max(dp[i][j][1], dp[i-1][j][3] + cell[i-1][j-1])

def __starting_point():
    main()

__starting_point()

from numpy import zeros, int64
from numba import njit

R, C, K, *RCV = map(int64, open(0).read().split())
V = zeros((R + 1, C + 1), int64)
for r, c, v in zip(*[iter(RCV)] * 3):
    V[r][c] = v

@njit
def main():
    dp = zeros((R + 1, C + 1, 4), int64)
    for i in range(1, R + 1):
        for j in range(1, C + 1):

            vij = V[i][j]

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

    print(dp[R][C][3])

main()

from numba import jit
import numpy as np

@jit
def main():
    R, C, K = map(int, input().split())
    v_list = np.zeros((R+2,C+2), np.int64)
    for i in range(K):
        r, c, v = map(int, input().split())
        v_list[r][c] = v
    dp = np.zeros((R+2,C+2,4), np.int64)

    for i in range(R+1):
        for j in range(C+1):
            for n in range(4):
                dp[i+1][j][n] = max(dp[i+1][j][n], dp[i][j][n])
                dp[i][j+1][n] = max(dp[i][j+1][n], dp[i][j][n])
                if n <= 2:
                    dp[i+1][j][n+1] = max(dp[i+1][j][3], dp[i][j][3] + v_list[i+1][j])
                    dp[i][j+1][n+1] = max(dp[i][j+1][n+1], dp[i][j][n] + v_list[i][j+1])
    return dp[R][C][3]

print(main())

import sys
import numpy as np
from numba import njit, void, i8
input = sys.stdin.readline

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

    L_INF = int(1e17)
    dp = np.full((R+1, C+1, 4), -L_INF, dtype=np.int64)
    cell = np.full((R+1, C+1), 0, dtype=np.int64)

    for i in range(K):
        x, y, c = list(map(int, input().split()))
        cell[x-1][y-1] = c

    f(dp, cell, R, C)

    print((dp[R][C][3]))

@njit(void(i8[:,:,:],i8[:,:],i8,i8))
def f(dp, cell, R, C):
    dp[0][1][0] = dp[1][0][0] = 0
    for i in range(1, R + 1):
        for j in range(1, C + 1):
            for k in range(4):
                if k > 0:
                    dp[i][j][k] = max(dp[i][j][k], dp[i][j][k-1])
                dp[i][j][k] = max(dp[i][j][k], dp[i][j-1][k])
                if k > 0:
                    dp[i][j][k] = max(dp[i][j][k], dp[i][j-1][k-1] + cell[i-1][j-1])
                if k == 1:
                    dp[i][j][k] = max(dp[i][j][1], dp[i-1][j][3] + cell[i-1][j-1])

def __starting_point():
    main()

__starting_point()

# Date [ 2020-08-15 21:54:45 ]
# Problem [ e.py ]
# Author Koki_tkg

import sys;      from decimal import Decimal
import math;     from itertools import combinations, product
import bisect;   from collections import Counter, deque, defaultdict

# sys.setrecursionlimit(10 ** 6)
MOD = 10 ** 6 + 7
INF = 10 ** 9
PI = 3.14159265358979323846

def read_str():      return sys.stdin.readline().strip()
def read_int():      return int(sys.stdin.readline().strip())
def read_ints():     return map(int, sys.stdin.readline().strip().split())
def read_str_list(): return list(sys.stdin.readline().strip().split())
def read_int_list(): return list(map(int, sys.stdin.readline().strip().split()))
def lcm(a: int, b: int) -> int: return (a * b) // math.gcd(a, b)

from numba import njit, i8
import numpy as np

@njit(i8(i8, i8, i8[:,:]))
def dp(R, C, grid):
    dp = np.zeros((R+1, C+1, 4), np.int64)
    for y in range(1, R+1):
        for x in range(1, C+1):
            for i in range(4):
                dp[y][x][i] = max(dp[y][x - 1][i], dp[y - 1][x][3])
            for i in range(3, 0, -1):
                dp[y][x][i] = max(dp[y][x][i], dp[y][x][i - 1] + grid[y-1][x-1])
    return dp[R][C][3]

def Main():
    R, C, k = read_ints()
    item = [read_int_list() for _ in range(k)]
    grid = np.zeros((R, C), np.int64)
    for r, c, v in item:
        grid[r - 1][c - 1] = v
    print(dp(R, C, grid))

if __name__ ==  '__main__':
    Main()

import sys
import numpy as np
from collections import defaultdict
from numba import njit
def input(): return sys.stdin.readline().rstrip()

@njit('i8[:](i8[:],i8[:,:])')
def koushin(dp,item):
    dptmp1 = np.copy(dp)
    dptmp2 = np.copy(dp)
    dptmp3 = np.copy(dp)
    for i in range(len(item)):
        dptmp3[item[i][0]:] = np.fmax(dptmp3[item[i][0]:], dptmp2[item[i][0]]+item[i][1])
        dptmp2[item[i][0]:] = np.fmax(dptmp2[item[i][0]:], dptmp1[item[i][0]]+item[i][1])
        dptmp1[item[i][0]:] = np.fmax(dptmp1[item[i][0]:], dp[item[i][0]]+item[i][1])
    return dptmp3

def main():
    R, C, K = list(map(int, input().split()))
    items = defaultdict(list)
    for _ in range(K):
        r, c, v = list(map(int, input().split()))
        items[r-1].append([c-1, v])
    dp = np.zeros(C, dtype='int64')
    for RR in range(R):
        if items[RR]==[]:
          continue
        items[RR].sort(key=lambda x: x[0])
        dp=koushin(dp,np.array(items[RR],dtype='int64'))
    print((dp[-1]))


def __starting_point():
    main()

__starting_point()

from numba import jit
import numpy as np

@jit
def main():
    R, C, K = map(int, input().split())
    scores = np.zeros((R,C), np.int64)
    for _ in range(K):
        r, c, v = map(int, input().split())
        scores[r-1][c-1] = v
    dp=np.zeros((R+1,C+1,4), np.int64)

    for i in range(1, R+1):
        for j in range(1, C+1):
            for k in range(4):
                dp[i][j][k] = max(dp[i][j-1][k],
                                dp[i-1][j][3])
            for k in range(3, 0, -1):
                dp[i][j][k] = max(dp[i][j][k],
                                  dp[i][j][k-1] + scores[i-1][j-1])

    
    return dp[R][C][3]

print(main())

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)))

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): # move downside without selecting
                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)
"""

import numba
from numba import jit
import numpy as np

#(i,j)→(i+1,j)のように動くときはアイテムを入手できる回数がリセットされる
#dp[列][今、何個アイテムを取ったか]でdpテーブルを作る
@jit
def main(r, c):
  dp = np.zeros((c+1, 4), np.int64)
  for i in range(r):
    new_dp = np.zeros((c+1, 4), np.int64)
    for j in range(4):
      new_dp[:,0] = np.maximum(new_dp[:,0], dp[:,j])
    dp = new_dp
    for k in range(c):
      for l in range(2, -1, -1):
        dp[k,l+1] = max(dp[k,l+1], dp[k,l]+item_map[i,k])
      for m in range(1,4):
        dp[k+1,m] = max(dp[k+1,m], dp[k,m])
  return max(dp[c-1,:])

R, C, K = list(map(int, input().split()))
item_lis = list(list(map(int, input().split())) for i in range(K))
item_map = np.zeros((R, C), np.int64)
for i,j,k in item_lis:
  item_map[i-1,j-1] = k

print((main(R, C)))


import numpy as np
from numba import jit

R, C, K = list(map(int, input().split()))
G = np.zeros((R+1, C+1), np.int64)
for i in range(K):
    [r, c, v] = list(map(int, input().split()))
    G[r-1][c-1] = v

@jit
def main(G, R, C):
    dp = np.full((R+1, C+1, 4), -1)
    dp[0][0][0] = 0
    if G[0][0] != None: dp[0][0][1] = G[0][0]
    for r in range(R):
        for c in range(C):
            for k in range(4):
                if dp[r][c][k] == -1: continue
                if k < 3: # can go right and pick up
                    if dp[r][c+1][k+1] < dp[r][c][k] + G[r][c+1]:
                        dp[r][c+1][k+1] = dp[r][c][k] + G[r][c+1]
                if dp[r][c+1][k] < dp[r][c][k]:
                    dp[r][c+1][k] = dp[r][c][k]
                if dp[r+1][c][0] < dp[r][c][k]:
                    dp[r+1][c][0] = dp[r][c][k]
                if dp[r+1][c][1] < dp[r][c][k] + G[r+1][c]:
                    dp[r+1][c][1] = dp[r][c][k] + G[r+1][c]
    return(max(dp[r][c]))

ret = main(G, R, C)
print(ret)            


from numba import jit
import numpy as np
@jit
def main():
  R,C,K=list(map(int,input().split()))
  scores=np.zeros((R,C),np.int64)
  for _ in range(K): #各マスにアイテム配置
    r,c,v=list(map(int,input().split()))
    scores[r-1][c-1]=v
  dp=np.zeros((R+1,C+1,4),np.int64) #後のために余分に作っておく、scoresの配列は別なのでindexに注意
  for i in range(1,R+1):
    for j in range(1,C+1):
      for k in range(4):
        dp[i][j][k]=max(dp[i][j-1][k],dp[i-1][j][3]) #同じ行ですでに3つ拾ってから次の行にくるのかただ隣のマスに進むか
      for k in range(3,0,-1):
        dp[i][j][k]=max(dp[i][j][k],dp[i][j][k-1]+scores[i-1][j-1]) #そのマスでアイテムを拾うかどうか
  return dp[R][C][3]
print((main()))


import numpy as np
from numba import jit


def test():
    R, C, K = list(map(int, input().split()))
    rcv = [list(map(int, input().split())) for _ in range(K)]

    items = np.zeros((R+1, C+1), dtype='int64')
    for item in rcv:
        items[item[0]][item[1]] = item[2]

    dp = np.zeros((R+1, C+1), dtype='int64')

    # まずは3個の制約がない場合での実装
    for j in range(1, R+1):
        for i in range(1, C+1):
            # 下に行く遷移
            dp[j][i] = max(dp[j][i], dp[j-1][i] + items[j][i])

            # 右に行く遷移
            dp[j][i] = max(dp[j][i], dp[j][i-1] + items[j][i])

    print((dp[R][C]))


@jit
def main(R, C, items):

    dp = np.zeros((4, R+1, C+1), dtype=np.int64)

    # 3個の制約がある場合の実装
    for i in range(1, R+1):
        for j in range(1, C+1):
            for k in range(4):
                # 下に行く遷移
                # 取らない場合
                dp[0][i][j] = max(dp[0][i][j], dp[k][i-1][j])
                # 取る場合
                dp[1][i][j] = max(dp[1][i][j], dp[k][i-1][j] + items[i][j])

                # 右に行く遷移
                # 取らない場合
                dp[k][i][j] = max(dp[k][i][j], dp[k][i][j-1])
                # 取る場合
                if k > 0:
                    dp[k][i][j] = max(dp[k][i][j], dp[k-1]
                                      [i][j-1] + items[i][j])

    ans = 0
    for k in range(4):
        if ans < dp[k][R][C]:
            ans = dp[k][R][C]

    print(ans)


def __starting_point():
    R, C, K = list(map(int, input().split()))
    rcv = [list(map(int, input().split())) for _ in range(K)]
    items = np.zeros((R+1, C+1), dtype=np.int64)
    for item in rcv:
        items[item[0]][item[1]] = item[2]
    main(R, C, items)

__starting_point()

from numba import jit
import numpy as np

@jit
def main():
    R, C, K = map(int, input().split())
    scores = np.zeros((R,C), np.int64)
    for _ in range(K):
        r, c, v = map(int, input().split())
        scores[r-1][c-1] = v
    dp = np.zeros((R+1,C+1,4), np.int64)

    for i in range(1, R+1):
        for j in range(1, C+1):
            for k in range(4):
                dp[i][j][k] = max(dp[i][j-1][k],
                                  dp[i-1][j][3])
            for k in range(3, 0, -1):
                dp[i][j][k] = max(dp[i][j][k],
                                  dp[i][j][k-1] + scores[i-1][j-1])

    return dp[R][C][3]

print(main())

import numpy as np
import sys
input = sys.stdin.readline


def main():
    h, w, k = list(map(int, input().split()))
    values = np.zeros((h, w), dtype=np.int64)
    items = np.array([list(map(int, input().split())) for _ in range(k)])
    ys, xs, vs = items[:, 0] - 1, items[:, 1] - 1, items[:, 2]
    values[ys, xs] = vs

    DP = np.zeros(w + 1, dtype=np.int64)
    for line in values:
        DP[1:] += line
        DP = np.maximum.accumulate(DP)
        for _ in range(2):
            DP[1:] = np.maximum(DP[:-1] + line, DP[1:])
            DP = np.maximum.accumulate(DP)
    print((DP[-1]))


def __starting_point():
    main()

__starting_point()

from numba import jit
import numpy as np
import sys

def input():
    return sys.stdin.readline()[:-1]
@jit
def main():
    R, C, K = list(map(int, input().split()))
    item = np.zeros((R,C), np.int64)
    for i in range(K):
        r,c,v = list(map(int,input().split()))
        item[r-1][c-1] = v

    dp = np.zeros((R+1,C+1,4), 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] + item[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 max(dp[R-1][C-1])
print((main()))


import sys
import numpy as np
from numba import njit

R, C, K = map(int, input().split())
item = np.zeros((R, C), np.int_)
for s in sys.stdin.readlines():
    r, c, v = map(int, s.split())
    item[r-1,c-1] = v

@njit
def solve(R, C, K, item):
    DP = np.zeros((R, C, 4), np.int_)

    DP[0][0][1] = item[0][0]

    for i in range(R):
        for j in range(C):
            for k in range(4):
                if i > 0:  # 前の行から
                    DP[i,j,0] = max(DP[i,j,0], max(DP[i-1,j]))  # 取らない
                    DP[i,j,1] = max(DP[i,j,1], max(DP[i-1,j])+item[i,j])  # 取る

                if j > 0:  # 前の列から
                    DP[i,j,k] = max(DP[i,j,k], DP[i,j-1,k])  # 取らない
                    if k >= 1:
                        DP[i,j,k] = max(DP[i,j,k], DP[i,j-1,k-1]+item[i,j])  # 取る

    print(max(DP[R-1,C-1]))

solve(R, C, K, item)