AtCoder Beginner Contest 175 - Picking Goods

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.

Source: atcoder | Difficulty: MEDIUM_HARD


Solutions:
(R, C, k) = map(int, input().split())
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)]
item = [[0] * (C + 1) for i in range(R + 1)]
for i in range(k):
	(r, c, v) = map(int, input().split())
	dp1[r][c] = v
for i in range(1, R + 1):
	for j in range(1, C + 1):
		a = dp1[i][j]
		dp3[i][j] = max(dp2[i][j - 1] + a, dp3[i][j - 1])
		dp2[i][j] = max(dp1[i][j - 1] + a, dp2[i][j - 1])
		dp1[i][j] = max(dp1[i - 1][j] + a, dp2[i - 1][j] + a, dp3[i - 1][j] + a, dp1[i][j - 1], a)
print(max(dp1[R][C], dp2[R][C], dp3[R][C]))


import sys
(R, C, K) = map(int, input().split())
item = [[0] * (C + 1) for _ in range(R + 1)]
for s in sys.stdin.readlines():
	(r, c, v) = 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)
				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)


import sys
from itertools import product
input = lambda : sys.stdin.buffer.readline().rstrip()
(m, n, k) = map(int, input().split())
grid = [[0] * n for _ in range(m)]
for _ in range(k):
	(i, j, v) = map(int, input().split())
	i -= 1
	j -= 1
	grid[i][j] = v
dp = [[0] * 4 for _ in range(n)]
for i in range(m):
	ndp = [[0] * 4 for _ in range(n)]
	for (j, k) in product(range(n), range(4)):
		ndp[j][0] = max(ndp[j][0], dp[j][k])
		ndp[j][1] = max(ndp[j][1], dp[j][k] + grid[i][j])
		if j > 0:
			ndp[j][k] = max(ndp[j][k], ndp[j - 1][k])
			if k > 0:
				ndp[j][k] = max(ndp[j][k], ndp[j - 1][k - 1] + grid[i][j])
	dp = ndp
print(max(dp[-1]))


def main():
	(R, C, K) = map(int, input().split())
	a = dict()
	for _ in range(K):
		(r, c, v) = map(int, input().split())
		a[r - 1, c - 1] = v
	dp = [[[0] * 4 for _ in range(C + 1)] for _ in range(2)]
	for i in range(R):
		for j in range(C):
			v = max(dp[0][j + 1])
			u = 0
			if (i, j) in a:
				u = a[i, j]
			dp[1][j + 1][0] = max(dp[1][j + 1][0], v)
			dp[1][j + 1][1] = max(dp[1][j + 1][1], dp[1][j][1], dp[1][j][0] + u, v + u)
			dp[1][j + 1][2] = max(dp[1][j + 1][2], dp[1][j][2], dp[1][j][1] + u)
			dp[1][j + 1][3] = max(dp[1][j + 1][3], dp[1][j][3], dp[1][j][2] + u)
		(dp[1], dp[0]) = (dp[0], dp[1])
	return max(dp[0][C])
print(main())


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


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
input = sys.stdin.readline
(R, L, K) = map(int, input().split())
V = [0] * (R * L)
for _ in range(K):
	(r, c, v) = map(int, input().split())
	V[(c - 1) * R + (r - 1)] = v
(A, B, C, D) = [[0] * (R + 1) for _ in range(4)]
for i in range(L):
	for j in range(R):
		A[j] = max(A[j - 1], B[j - 1], C[j - 1], D[j - 1])
		v = V[i * R + j]
		if v != 0:
			(D[j], C[j], B[j]) = (max(C[j] + v, D[j]), max(B[j] + v, C[j]), max(A[j] + v, B[j]))
print(max(A[-2], B[-2], C[-2], D[-2]))


import sys
input = sys.stdin.readline
(R, C, K) = map(int, input().split())
dp = [[0] * 4 for i in range(C + 1)]
prev = [0] * (C + 1)
tb = [[0] * (C + 1) for i in range(R + 1)]
for i in range(K):
	(r, c, v) = map(int, input().split())
	tb[r][c] = v
for i in range(1, R + 1):
	for j in range(1, C + 1):
		pmx = 0
		for k in range(4):
			mx = dp[j - 1][k]
			if k > 0:
				mx = max(mx, dp[j - 1][k - 1] + tb[i][j])
			if k == 0:
				mx = max(mx, prev[j])
			elif k == 1:
				mx = max(mx, prev[j] + tb[i][j])
			dp[j][k] = mx
			pmx = max(pmx, mx)
		prev[j] = pmx
print(prev[C])


(R, C, K) = map(int, input().split())
I = [[0 for _ in range(C + 1)] for _ in range(R + 1)]
for i in range(K):
	(r, c, v) = map(int, input().split())
	I[r][c] = v
DP1 = [0 for _ in range(C + 1)]
DP2 = [0 for _ in range(C + 1)]
DP3 = [0 for _ in range(C + 1)]
for r in range(1, R + 1):
	for c in range(1, C + 1):
		mid = DP3[c] + I[r][c]
		DP3[c] = max(DP3[c - 1], mid, DP2[c - 1] + I[r][c])
		DP2[c] = max(DP2[c - 1], mid, DP1[c - 1] + I[r][c])
		DP1[c] = max(DP1[c - 1], mid)
print(DP3[C])


def solve():
	(R, C, K) = map(int, input().split())
	item = [[0] * C for _ in range(R)]
	for i in range(K):
		(r, c, v) = map(int, input().split())
		item[r - 1][c - 1] = v
	last_dp = [[0] * (C + 1) for _ in range(5)]
	for i in range(1, R + 1):
		dp = [[0] * (C + 1) for _ in range(5)]
		for j in range(1, C + 1):
			for k in range(4):
				dp[k][j] = dp[k][j - 1]
			dp[0][j] = max(dp[0][j], last_dp[-1][j])
			if item[i - 1][j - 1] > 0:
				dp[1][j] = max(dp[1][j], last_dp[-1][j] + item[i - 1][j - 1])
				for k in range(1, 4):
					dp[k][j] = max(dp[k][j], dp[k - 1][j - 1] + item[i - 1][j - 1])
			for k in range(4):
				dp[-1][j] = max(dp[-1][j], dp[k][j])
		last_dp = dp
	ans = last_dp[-1][-1]
	return ans
print(solve())


(r, c, k) = map(int, input().split())
v = [[0 for _ in range(c)] for _ in range(r)]
for _ in range(k):
	(ri, ci, vi) = map(int, input().split())
	v[ri - 1][ci - 1] = vi
dp = [[0, 0, 0, 0] for _ in range(c)]
for i in range(r):
	for j in range(c):
		dpj = dp[j][:]
		if j == 0:
			dp[j] = [max(dpj), max(dpj) + v[i][j], 0, 0]
		else:
			dp[j][0] = max(max(dpj), dp[j - 1][0])
			dp[j][1] = dp[j - 1][1]
			dp[j][2] = dp[j - 1][2]
			dp[j][3] = dp[j - 1][3]
			if v[i][j] > 0:
				dp[j][1] = max(dp[j][1], dp[j - 1][0] + v[i][j], max(dpj) + v[i][j])
				dp[j][2] = max(dp[j][2], dp[j - 1][1] + v[i][j])
				dp[j][3] = max(dp[j][3], dp[j - 1][2] + v[i][j])
print(max(dp[c - 1]))


import sys
input = sys.stdin.readline
(R, C, K) = map(int, input().split())
J = [tuple(map(int, input().split())) for i in range(K)]
DP1 = [[0] * (C + 2) for i in range(R + 2)]
DP2 = [[0] * (C + 2) for i in range(R + 2)]
DP3 = [[0] * (C + 2) for i in range(R + 2)]
MAP = [[0] * C for i in range(R)]
for (x, y, v) in J:
	MAP[x - 1][y - 1] = v
for i in range(R):
	for j in range(C):
		DP1[i][j] = max(DP1[i][j - 1], DP1[i - 1][j] + MAP[i][j], DP2[i - 1][j] + MAP[i][j], DP3[i - 1][j] + MAP[i][j])
		DP2[i][j] = max(DP2[i][j - 1], DP1[i][j - 1] + MAP[i][j])
		DP3[i][j] = max(DP3[i][j - 1], DP2[i][j - 1] + MAP[i][j])
ANS = 0
for i in range(R):
	for j in range(C):
		ANS = max(ANS, DP1[i][j], DP2[i][j], DP3[i][j])
print(ANS)


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


((R, C, K), *t) = [map(int, t.split()) for t in open(0)]
(G, *F) = eval("eval('[0]*-~C,'*R)," * 5)
for (r, c, v) in t:
	G[r - 1][c] = v
for r in range(R):
	for x in (1, 2, 3):
		for c in range(C):
			F[x][r][c] = max(F[x - 1][r][c], max(F[x - 1][r][c - 1], (x < 2) * F[3][r - 1][c]) + G[r][c + 1], F[x][r][c - 1])
print(F[3][-1][-2])


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


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


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) = 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 _ in range(R + 1)]
	for i in range(R):
		v = [0] * 4
		for j in range(C):
			for k in range(4):
				if v[k] < dp[i][j + 1]:
					v[k] = dp[i][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[i + 1][j + 1] = v[3]
	print(dp[R][C])
	return
main()


(R, C, K) = map(int, input().split())
V = [[] for i in range(R)]
for i in range(K):
	(r, c, v) = map(int, input().split())
	V[r - 1].append([c, v])
cost = [0] * (C + 1)
for r in range(R):
	V[r].sort()
	hoge = [0, 0, 0, 0]
	for (c, v) in V[r]:
		for i in range(3, 0, -1):
			hoge[i] = max(cost[c] + v, hoge[i - 1] + v, hoge[i])
		hoge[0] = cost[c]
		cost[c] = max(hoge)
	for i in range(1, C + 1):
		cost[i] = max(cost[i], cost[i - 1])
print(cost[-1])


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


(R, C, k) = map(int, input().split())
rcv = [[0 for _ in range(C + 1)] for _ in range(R + 1)]
for i in range(k):
	(r, c, v) = map(int, input().split())
	rcv[r][c] = v
dp0 = [[0 for _ in range(C + 1)] for _ in range(R + 1)]
dp1 = [[0 for _ in range(C + 1)] for _ in range(R + 1)]
dp2 = [[0 for _ in range(C + 1)] for _ in range(R + 1)]
dp3 = [[0 for _ in range(C + 1)] for _ in range(R + 1)]
dp1[1][1] = rcv[1][1]
for r in range(1, R + 1):
	for c in range(1, C + 1):
		dp1[r][c] = max(dp0[r][c] + rcv[r][c], dp0[r][c - 1] + rcv[r][c], dp1[r][c - 1])
		dp2[r][c] = max(dp1[r][c - 1] + rcv[r][c], dp2[r][c - 1])
		dp3[r][c] = max(dp2[r][c - 1] + rcv[r][c], dp3[r][c - 1])
		if r < R:
			dp0[r + 1][c] = max(dp0[r][c], dp1[r][c], dp2[r][c], dp3[r][c])
print(max(dp0[R][C], dp1[R][C], dp2[R][C], dp3[R][C]))


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


(R, C, K) = map(int, input().split())
items = [[0 for _ in range(C + 1)] for _ in range(R + 1)]
for i in range(K):
	(r, c, v) = map(int, input().split())
	items[r][c] = v
DP_prev = [0 for _ in range(C + 1)]
for r in range(1, R + 1):
	DP = [[0 for _ in range(C + 1)], [0 for _ in range(C + 1)], [0 for _ in range(C + 1)]]
	for c in range(1, C + 1):
		item = items[r][c]
		DP1 = max(DP_prev[c] + item, DP[0][c - 1])
		DP2 = max(DP1, DP[1][c - 1], DP[0][c - 1] + item)
		DP3 = max(DP2, DP[2][c - 1], DP[1][c - 1] + item)
		DP[0][c] = DP1
		DP[1][c] = DP2
		DP[2][c] = DP3
	DP_prev = DP[2]
print(DP_prev[C])


import sys
input = sys.stdin.readline
(R, C, K) = list(map(int, input().split()))
itemMap = [[0] * (C + 1) for _ in range(R + 1)]
dp = [[[0] * (C + 1) for _ in range(R + 1)] for _ in range(4)]
for _ in range(K):
	(r, c, v) = list(map(int, input().split()))
	itemMap[r - 1][c - 1] = v
for ir in range(R):
	for ic in range(C):
		for k in range(2, -1, -1):
			dp[k + 1][ir][ic] = max(dp[k + 1][ir][ic], dp[k][ir][ic] + itemMap[ir][ic])
		for k in range(4):
			dp[0][ir + 1][ic] = max(dp[0][ir + 1][ic], dp[k][ir][ic])
			dp[k][ir][ic + 1] = max(dp[k][ir][ic + 1], dp[k][ir][ic])
ans = 0
for k in range(4):
	ans = max(ans, dp[k][R - 1][C - 1])
print(ans)


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


import sys
readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda : readline().rstrip()
ni = lambda : int(readline().rstrip())
nm = lambda : map(int, readline().split())
nl = lambda : list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

def solve():
	(h, w, k) = nm()
	d = dict()
	for _ in range(k):
		(r, c, v) = nm()
		d[r * 10000 + c - 10001] = v
	prv = [[0] * 4 for _ in range(w + 1)]
	nxt = [[0] * 4 for _ in range(w + 1)]
	for i in range(h):
		for j in range(w):
			f = d.get(i * 10000 + j, 0)
			t = max(prv[j])
			for v in range(4):
				nxt[j][v] = max(nxt[j - 1][v], t)
				if v:
					nxt[j][v] = max(nxt[j][v], nxt[j - 1][v - 1] + f, t + f)
		(prv, nxt) = (nxt, prv)
	print(max(prv[w - 1]))
	return
solve()


(f, g, h) = (range, max, input)
(R, C, K) = map(int, h().split())
G = [[0] * -~C for i in f(R + 1)]
for i in '_' * K:
	(r, c, v) = map(int, h().split())
	G[r][c] = v
F = [[[0] * -~C for i in f(R + 1)] for i in f(4)]
for r in f(1, R + 1):
	for x in f(1, 4):
		for c in f(1, C + 1):
			F[x][r][c] = g(F[x - 1][r][c], F[x - 1][r][c - 1] + G[r][c], F[x][r][c - 1], (x < 2) * (G[r][c] + F[3][r - 1][c]))
print(F[3][R][C])


import sys

def input():
	return sys.stdin.readline().strip()

def mapint():
	return 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]))


(R, C, K) = map(int, input().split())
V = [[0] * (C + 1) for _ in range(R + 1)]
for _ in range(K):
	(r, c, v) = map(int, input().split())
	V[r][c] = v
pre0 = [0] * (C + 1)
pre1 = [0] * (C + 1)
pre2 = [0] * (C + 1)
pre3 = [0] * (C + 1)
for i in range(R + 1):
	now0 = [0] * (C + 1)
	now1 = [0] * (C + 1)
	now2 = [0] * (C + 1)
	now3 = [0] * (C + 1)
	for j in range(C + 1):
		v = V[i][j]
		la = lb = 0
		if j > 0:
			la = now0[j - 1]
			lb = now1[j - 1]
			now2[j] = max(now2[j], now2[j - 1], lb + v)
			now3[j] = max(now3[j], now3[j - 1], now2[j - 1] + v)
		if i > 0:
			max_p = max(pre0[j], pre1[j], pre2[j], pre3[j])
			now0[j] = max(now0[j], max_p, la)
			now1[j] = max(now1[j], max_p + v, la + v, lb)
	pre0 = now0
	pre1 = now1
	pre2 = now2
	pre3 = now3
print(max(now0[C], now1[C], now2[C], now3[C]))


import sys

def input():
	return sys.stdin.readline().rstrip()
(R, C, k) = (int(x) for x in input().split())
V = [[0] * (C + 5) for _ in range(R + 5)]
for _ in range(k):
	(r, c, v) = (int(x) for x in input().split())
	V[r][c] = v
dp = [[[0] * (C + 5) for _ in range(R + 5)] for _ in range(4)]
for i in range(R + 3):
	for j in range(C + 3):
		for k in range(4):
			dp[0][i + 1][j] = max(dp[0][i + 1][j], dp[k][i][j])
			dp[1][i + 1][j] = max(dp[1][i + 1][j], dp[k][i][j] + V[i + 1][j])
			dp[k][i][j + 1] = max(dp[k][i][j + 1], dp[k][i][j])
			if k < 3:
				dp[k + 1][i][j + 1] = max(dp[k + 1][i][j + 1], dp[k][i][j] + V[i][j + 1])
print(max((dp[k][R][C] for k in range(4))))


def main():
	(r, c, k) = map(int, input().split())
	d = [[0] * c for _ in [0] * r]
	for _ in range(k):
		(t1, t2, t3) = map(int, input().split())
		d[t1 - 1][t2 - 1] = t3
	dp = [[0] * 4 for _ in [0] * c]
	dp[0][1] = d[0][0]
	for x in range(r):
		dp2 = [[0] * 4 for _ in [0] * c]
		for y in range(c):
			for z in range(4):
				if y != c - 1:
					if z != 3:
						dp[y + 1][z + 1] = max(dp[y + 1][z + 1], dp[y][z] + d[x][y + 1])
					dp[y + 1][z] = max(dp[y + 1][z], dp[y][z])
			if x != r - 1:
				dp2[y][1] = max(dp2[y][1], max(dp[y]) + d[x + 1][y])
				dp2[y][0] = max(dp2[y][0], max(dp[y]))
		if x != r - 1:
			dp = dp2
	print(max(dp[c - 1]))
main()


import sys
input = lambda : sys.stdin.readline().rstrip()
(r, c, k) = map(int, input().split())
D = [[0] * c for _ in range(r)]
for _ in range(k):
	(ri, ci, v) = map(int, input().split())
	ri -= 1
	ci -= 1
	D[ri][ci] = v
DP = [[[0] * (c + 1) for _ in range(r + 1)] for i in range(4)]
for i in range(r):
	for j in range(c):
		v = D[i][j]
		for ii in range(4):
			DP[0][i][j] = max(DP[0][i][j], DP[ii][i - 1][j])
			if v != 0:
				DP[1][i][j] = max(DP[1][i][j], DP[ii][i - 1][j] + v)
			DP[ii][i][j] = max(DP[ii][i][j], DP[ii][i][j - 1])
			if v != 0 and ii != 0:
				DP[ii][i][j] = max(DP[ii][i][j], DP[ii - 1][i][j - 1] + v)
ans = 0
for i in range(4):
	ans = max(ans, DP[i][r - 1][c - 1])
print(ans)


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


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


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


import sys
input = lambda : sys.stdin.readline().rstrip()
(r, c, k) = map(int, input().split())
dp = [[(c + 1) * [0] for _ in range(r + 1)] for _ in range(4)]
p = [c * [0] for _ in range(r)]
for _ in range(k):
	(rr, cc, u) = map(int, input().split())
	rr -= 1
	cc -= 1
	p[rr][cc] = u
ans = 0
for j in range(1, r + 1):
	for k in range(1, c + 1):
		dp[0][j][k] = max(dp[0][j - 1][k], dp[0][j][k - 1])
		t = max(dp[0][j - 1][k], dp[1][j - 1][k], dp[2][j - 1][k], dp[3][j - 1][k])
		for i in range(1, 4):
			dp[i][j][k] = max(dp[i][j][k], t, dp[i][j][k - 1])
			if p[j - 1][k - 1]:
				dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j][k - 1] + p[j - 1][k - 1], t + p[j - 1][k - 1])
			ans = max(ans, dp[i][j][k])
print(ans)


import sys
input = sys.stdin.readline

def main():
	(R, C, K) = map(int, input().split())
	lis = [[0] * C for i in range(R)]
	for i in range(K):
		(a, b, c) = map(int, input().split())
		lis[a - 1][b - 1] = c
	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):
			for (x, y) in ((dp0, 0), (dp1, dp0), (dp2, dp1), (dp3, dp2)):
				t = lis[i - 1][j - 1]
				x[i][j] = max(x[i - 1][j], x[i][j])
				x[i][j] = max(x[i][j - 1], x[i][j])
				if t != 0:
					dp1[i][j] = max(dp1[i][j], x[i - 1][j] + t)
					if y != 0:
						x[i][j] = max(x[i][j], y[i][j - 1] + t)
	print(max(dp0[-1][-1], dp1[-1][-1], dp2[-1][-1], dp3[-1][-1]))
main()


import sys
input = sys.stdin.readline

def solve():
	INF = float('inf')

	def max2(x, y):
		return x if x >= y else y
	(R, C, K) = map(int, input().split())
	Vss = [[0] * (C + 1) for _ in range(R + 1)]
	for _ in range(K):
		(r, c, v) = map(int, input().split())
		Vss[r][c] = v
	dpMax = [0] * (C + 1)
	for i in range(1, R + 1):
		dp0 = [0] * (C + 1)
		dp1 = [-INF] * (C + 1)
		dp2 = [-INF] * (C + 1)
		dp3 = [-INF] * (C + 1)
		for j in range(1, C + 1):
			V = Vss[i][j]
			dp0[j] = max2(dp0[j - 1], dpMax[j])
			dp1[j] = max2(dp0[j] + V, dp1[j - 1])
			dp2[j] = max2(dp1[j - 1] + V, dp2[j - 1])
			dp3[j] = max2(dp2[j - 1] + V, dp3[j - 1])
			dpMax[j] = max(dp0[j], dp1[j], dp2[j], dp3[j])
	ans = dpMax[C]
	print(ans)
solve()


(R, C, K) = map(int, input().split())
MAP = [[0 for i in range(C)] for j in range(R)]
DP = [[[0 for i in range(C + 1)] for j in range(4)] for k in range(R + 1)]
for _ in range(K):
	(r, c, v) = map(int, input().split())
	MAP[r - 1][c - 1] = v
for i in range(R):
	for j in range(4):
		for k in range(C):
			DP[i + 1][j][k + 1] = max(DP[i][3][k + 1], DP[i + 1][j][k])
			if j == 0:
				continue
			v = MAP[i][k]
			if v == 0:
				continue
			DP[i + 1][j][k + 1] = max(DP[i + 1][j][k + 1], max(DP[i][3][k + 1], DP[i + 1][j - 1][k]) + v)
print(DP[R][3][C])


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)


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


import sys
(R, C, K) = list(map(int, input().split()))
d = [[[0] * (C + 1) for _ in range(R + 1)] for _ in range(4)]
t = [[0] * (C + 1) for _ in range(R + 1)]
for i in range(K):
	(r, c, v) = list(map(int, input().split()))
	t[r][c] = v
for i in range(R + 1):
	for j in range(C + 1):
		for k in range(4):
			if i != 0:
				d[0][i][j] = max(d[0][i][j], d[k][i - 1][j])
				d[1][i][j] = max(d[1][i][j], d[k][i - 1][j] + t[i][j])
			if j != 0:
				d[k][i][j] = max(d[k][i][j], d[k][i][j - 1])
				if k != 0:
					d[k][i][j] = max(d[k][i][j], d[k - 1][i][j - 1] + t[i][j])
a = 0
for i in range(4):
	a = max(a, d[i][-1][-1])
print(a)


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


(R, C, K) = map(int, input().split())
grid = [[0] * C for _ in range(R)]
for i in range(K):
	(x, y, v) = map(int, input().split())
	grid[x - 1][y - 1] = v
dp0 = [[0] * (C + 1) for _ in range(R + 1)]
dp1 = [[0] * (C + 1) for _ in range(R + 1)]
dp2 = [[0] * (C + 1) for _ in range(R + 1)]
dp3 = [[0] * (C + 1) for _ in range(R + 1)]
for i in range(R):
	for j in range(C):
		dp1[i][j] = max(dp1[i][j - 1], dp1[i - 1][j] + grid[i][j], dp2[i - 1][j] + grid[i][j], dp3[i - 1][j] + grid[i][j])
		dp2[i][j] = max(dp2[i][j - 1], dp1[i][j - 1] + grid[i][j])
		dp3[i][j] = max(dp3[i][j - 1], dp2[i][j - 1] + grid[i][j])
ans = max(dp1[R - 1][C - 1], dp2[R - 1][C - 1], dp3[R - 1][C - 1])
print(ans)


from collections import defaultdict
(R, C, K) = map(int, input().split())
rc2v = defaultdict(int)
for _ in range(K):
	(r, c, v) = map(int, input().split())
	r -= 1
	c -= 1
	rc2v[r, c] = v
dp = [0] * C
for r in range(R):
	dp_ = [[0] * C for _ in range(4)]
	for c in range(C):
		dp_[3][c] = max(dp_[3][c - 1], dp[c])
		dp_[2][c] = dp_[2][c - 1]
		dp_[1][c] = dp_[1][c - 1]
		dp_[0][c] = dp_[0][c - 1]
		if (r, c) in rc2v:
			dp_[0][c] = max(dp_[0][c - 1], dp_[1][c] + rc2v[r, c])
			dp_[1][c] = max(dp_[1][c - 1], dp_[2][c] + rc2v[r, c])
			dp_[2][c] = max(dp_[2][c - 1], dp_[3][c] + rc2v[r, c])
		dp[c] = max(dp_[3][c], dp_[2][c], dp_[1][c], dp_[0][c])
print(dp[-1])


import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
(R, C, K) = map(int, readline().split())
rcv = list(map(int, read().split()))
rc2v = {}
for (rr, cc, vv) in zip(rcv[::3], rcv[1::3], rcv[2::3]):
	rc2v[rr, cc] = vv
dp = [[0] * 4 for c in range(C + 1)]
for r in range(1, R + 1):
	for c in range(1, C + 1):
		v = rc2v[r, c] if (r, c) in rc2v else 0
		dp[c][0] = max(dp[c - 1][0], max(dp[c]))
		dp[c][1] = max(dp[c - 1][1], dp[c][0] + v)
		for k in range(2, 4):
			dp[c][k] = max(dp[c - 1][k], dp[c - 1][k - 1] + v)
print(max(dp[-1]))


(r, c, k) = map(int, input().split())
grid = [[0] * (c + 1) for _ in range(r + 1)]
for i in range(k):
	(ri, ci, vi) = map(int, input().split())
	grid[ri][ci] = vi
dp = [[[0] * (c + 1) for _ in range(r + 1)] for _ in range(4)]
for i in range(1, r + 1):
	for j in range(1, c + 1):
		for k in range(4):
			dp[0][i][j] = max(dp[0][i][j], dp[k][i - 1][j])
			dp[k][i][j] = max(dp[k][i][j], dp[k][i][j - 1])
		if grid[i][j] != 0:
			dp[1][i][j] = max(dp[1][i][j], dp[0][i - 1][j] + grid[i][j])
			for k in range(1, 4):
				dp[1][i][j] = max(dp[1][i][j], dp[k][i - 1][j] + grid[i][j])
				dp[k][i][j] = max(dp[k][i][j], dp[k - 1][i][j - 1] + grid[i][j])
ans = 0
for k in range(4):
	ans = max(ans, dp[k][-1][-1])
print(ans)


(R, C, K) = map(int, input().split())
point = [[0] * C for _ in range(R)]
for _ in range(K):
	(r, c, v) = map(int, input().split())
	point[r - 1][c - 1] = v
dp = [[[0] * C for _ in range(R)] for _ in range(4)]
dp[1][0][0] = point[0][0]
for i in range(R):
	for j in range(C - 1):
		for k in range(4):
			dp[k][i][j + 1] = max(dp[k][i][j + 1], dp[k][i][j])
			if k != 0:
				dp[k][i][j + 1] = max(dp[k][i][j + 1], dp[k - 1][i][j] + point[i][j + 1])
	if i == R - 1:
		break
	for j in range(C):
		mx = 0
		for k in range(4):
			mx = max(dp[k][i][j], mx)
		dp[0][i + 1][j] = mx
		dp[1][i + 1][j] = mx + point[i + 1][j]
ans = 0
for i in range(4):
	ans = max(ans, dp[i][R - 1][C - 1])
print(ans)


(r, c, k) = map(int, input().split())
v = [[0] * (c + 1) for i in range(r + 1)]
for i in range(k):
	(x, y, z) = map(int, input().split())
	v[x][y] = z
dp = [[0] * 4 for i in range(r + 1)]
for i in range(1, c + 1):
	for j in range(1, r + 1):
		if v[j][i] > 0:
			dp[j][3] = max(dp[j][2] + v[j][i], dp[j][3])
			dp[j][2] = max(dp[j][1] + v[j][i], dp[j][2])
			dp[j][1] = max(dp[j][0] + v[j][i], dp[j][1], max(dp[j - 1]) + v[j][i])
		dp[j][0] = max(dp[j][0], max(dp[j - 1]))
print(max(dp[r]))


(R, C, K) = map(int, input().split())
item = {}
for _ in range(K):
	(r, c, v) = map(int, input().split())
	item[r, c] = v
dp = [[0] * 4 for _ in range(3010)]
ndp = [[0] * 4 for _ in range(3010)]
for r in range(1, R + 1):
	for c in range(1, C + 1):
		prer = max(dp[c])
		ndp[c][0] = max(prer, ndp[c - 1][0])
		ndp[c][1] = max(prer, ndp[c - 1][1])
		ndp[c][2] = max(prer, ndp[c - 1][2])
		ndp[c][3] = max(prer, ndp[c - 1][3])
		if item.get((r, c)):
			ndp[c][1] = max(ndp[c][1], max(prer, ndp[c - 1][0]) + item[r, c])
			ndp[c][2] = max(ndp[c][2], max(prer, ndp[c - 1][1]) + item[r, c])
			ndp[c][3] = max(ndp[c][3], max(prer, ndp[c - 1][2]) + item[r, c])
	dp = ndp
	ndp = [[0] * 4 for _ in range(3010)]
print(max(dp[C]))


(r, c, k) = map(int, input().split())
dp = [[[0] * (c + 1) for _ in range(r + 1)] for _ in range(4)]
g = [[0] * (c + 1) for _ in range(r + 1)]
for _ in range(k):
	(a, b, v) = map(int, input().split())
	g[a][b] = v
for i in range(r + 1):
	for j in range(c + 1):
		for m in range(4):
			tmp = dp[m][i][j]
			if i + 1 <= r:
				dp[0][i + 1][j] = max(tmp, dp[0][i + 1][j])
				dp[1][i + 1][j] = max(dp[1][i + 1][j], tmp + g[i + 1][j])
			if j + 1 <= c:
				dp[m][i][j + 1] = max(dp[m][i][j + 1], tmp)
				if m < 3:
					dp[m + 1][i][j + 1] = max(dp[m + 1][i][j + 1], tmp + g[i][j + 1])
ans = 0
for m in range(4):
	ans = max(ans, dp[m][-1][-1])
print(ans)


(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
dp0 = [[0] * (C + 1) for _ in range(R + 1)]
dp1 = [[0] * (C + 1) for _ in range(R + 1)]
dp2 = [[0] * (C + 1) for _ in range(R + 1)]
dp3 = [[0] * (C + 1) for _ in range(R + 1)]
for r in range(R):
	for c in range(C):
		v = items[r][c]
		for (fr, to) in ((dp2, dp3), (dp1, dp2), (dp0, dp1)):
			to[r][c] = max(to[r][c], fr[r][c] + v)
		for dp in (dp0, dp1, dp2, dp3):
			dp[r][c + 1] = max(dp[r][c + 1], dp[r][c])
			dp0[r + 1][c] = max(dp0[r + 1][c], dp[r][c])
ans = max(dp0[R - 1][C], dp0[R][C - 1], dp1[R - 1][C], dp1[R][C - 1], dp2[R - 1][C], dp2[R][C - 1], dp3[R - 1][C], dp3[R][C - 1])
print(ans)


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


(R, C, K) = map(int, input().split())
xy = [[0] * (C + 1) for _ in range(R + 1)]
for _ in range(K):
	(r, c, v) = map(int, input().split())
	xy[r - 1][c - 1] = v
dp = [[[0] * (C + 1) for _ in range(R + 1)] for _ in range(4)]
for cy in range(R + 1):
	for cx in range(C + 1):
		if cx < C:
			dp[0][cy][cx + 1] = max(dp[0][cy][cx + 1], dp[0][cy][cx])
			dp[1][cy][cx + 1] = max(dp[1][cy][cx + 1], dp[0][cy][cx] + xy[cy][cx], dp[1][cy][cx])
			dp[2][cy][cx + 1] = max(dp[2][cy][cx + 1], dp[1][cy][cx] + xy[cy][cx], dp[2][cy][cx])
			dp[3][cy][cx + 1] = max(dp[3][cy][cx + 1], dp[2][cy][cx] + xy[cy][cx], dp[3][cy][cx])
		if cy < R:
			dp[0][cy + 1][cx] = max((dp[i][cy][cx] for i in range(3))) + xy[cy][cx]
			dp[0][cy + 1][cx] = max(dp[0][cy + 1][cx], dp[3][cy][cx])
print(max((dp[i][-1][-1] for i in range(4))))


(R, C, K) = list(map(int, input().split()))
V = [[] for i in range(R)]
for i in range(K):
	(r, c, v) = list(map(int, input().split()))
	V[r - 1].append([c, v])
dp = [0] * (C + 1)
for r in range(1, R + 1):
	tmp0 = 0
	tmp1 = 0
	tmp2 = 0
	tmp3 = 0
	V[r - 1].sort()
	for (c, v) in V[r - 1]:
		tmp0 = max(dp[c], tmp0)
		tmp1 = max(dp[c], tmp1)
		tmp2 = max(dp[c], tmp2)
		tmp3 = max(dp[c], tmp3)
		tmp3 = max(tmp3, tmp2 + v)
		tmp2 = max(tmp2, tmp1 + v)
		tmp1 = max(tmp1, tmp0 + v)
		dp[c] = max(tmp0, tmp1, tmp2, tmp3)
	for i in range(1, C + 1):
		dp[i] = max(dp[i], dp[i - 1])
print(dp[-1])


(R, C, K) = map(int, input().split())
p = []
for k in range(K):
	p.append(list(map(int, input().split())))
maps = [[0 for _ in range(C)] for _ in range(R)]
for k in range(K):
	maps[p[k][0] - 1][p[k][1] - 1] += p[k][2]
point1 = [[0 for _ in range(C)] for _ in range(R)]
point2 = [[0 for _ in range(C)] for _ in range(R)]
point3 = [[0 for _ in range(C)] for _ in range(R)]
point1[0][0] = maps[0][0]
for r in range(R):
	for c in range(C):
		(a, b, d) = (point1[r][c], point2[r][c], point3[r][c])
		if c < C - 1:
			x = maps[r][c + 1]
			point1[r][c + 1] = max(point1[r][c + 1], x, a)
			point2[r][c + 1] = max(point2[r][c + 1], a + x, b)
			point3[r][c + 1] = max(point3[r][c + 1], b + x, d)
		if r < R - 1:
			point1[r + 1][c] = maps[r + 1][c] + max(a, b, d)
print(max(point1[-1][-1], point2[-1][-1], point3[-1][-1]))


import sys
inp = [int(x) for x in sys.stdin.read().split()]
ii = 0
(r, c, k) = inp[ii:ii + 3]
ii += 3
v = [0] * (c * r)
for _ in range(k):
	(ri, ci, a) = inp[ii:ii + 3]
	ii += 3
	v[(ri - 1) * c + (ci - 1)] = a
dp = [0] * (c * r * 4)
x = c * r
if v[0] > 0:
	dp[x] = v[0]
for i in range(r):
	for j in range(c):
		idx = i * c + j
		idx2 = (i - 1) * c + j
		idx3 = i * c + j - 1
		val = v[idx]
		if i > 0:
			a = max(dp[idx2], dp[x + idx2], dp[2 * x + idx2], dp[3 * x + idx2])
			dp[idx] = a
			dp[x + idx] = a + val
		if j > 0:
			dp[idx] = max(dp[idx], dp[idx3])
			dp[x + idx] = max(dp[x + idx], dp[idx3] + val, dp[x + idx3])
			dp[2 * x + idx] = max(dp[x + idx3] + val, dp[2 * x + idx3])
			dp[3 * x + idx] = max(dp[2 * x + idx3] + val, dp[3 * x + idx3])
ans = 0
for i in range(4):
	ans = max(dp[i * x + (r - 1) * c + (c - 1)], ans)
print(ans)


(R, C, K) = map(int, input().split())
mp = [[0] * (C + 1) for _ in range(R + 1)]
for _ in range(K):
	(r, c, v) = map(int, input().split())
	mp[r][c] = v
memo = [[0] * 4 for _ in range(R + 1)]
for j in range(1, C + 1):
	for i in range(1, R + 1):
		if mp[i][j] > 0:
			memo[i][3] = max(memo[i][3], memo[i][2] + mp[i][j])
			memo[i][2] = max(memo[i][2], memo[i][1] + mp[i][j])
			memo[i][1] = max(memo[i][1], memo[i][0] + mp[i][j], max(memo[i - 1]) + mp[i][j])
			memo[i][0] = max(memo[i][0], max(memo[i - 1]))
		else:
			memo[i][0] = max(memo[i][0], max(memo[i - 1]))
print(max(memo[R]))


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


def main():
	import sys
	input = sys.stdin.readline
	(h, w, k) = map(int, input().split())
	H = range(h)
	W = range(w)
	dp = [[[0] * w for j in H] for i in range(4)]
	for _ in range(k):
		(r, c, v) = map(int, input().split())
		dp[0][r - 1][c - 1] = v
	if dp[0][0][0] != 0:
		dp[1][0][0] = dp[0][0][0]
		dp[0][0][0] = 0
	for y in H:
		for x in W:
			v = dp[0][y][x]
			dp[0][y][x] = 0
			for i in range(4):
				if 0 < x:
					if dp[i][y][x] < dp[i][y][x - 1]:
						dp[i][y][x] = dp[i][y][x - 1]
					if 0 < i and v != 0 and (dp[i][y][x] < dp[i - 1][y][x - 1] + v):
						dp[i][y][x] = dp[i - 1][y][x - 1] + v
				if 0 < y:
					if dp[0][y][x] < dp[i][y - 1][x]:
						dp[0][y][x] = dp[i][y - 1][x]
					if v != 0 and dp[1][y][x] < dp[i][y - 1][x] + v:
						dp[1][y][x] = dp[i][y - 1][x] + v
	print(max([dp[i][h - 1][w - 1] for i in range(4)]))
main()


(H, W, k) = map(int, input().split())
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)


(r, c, k) = map(int, input().split())
dp = [[[0] * (c + 1) for _ in range(r + 1)] for _ in range(4)]
v_dict = dict()
for _ in range(k):
	(y, x, v) = map(int, input().split())
	v_dict[y, x] = v
for y in range(1, r + 1):
	for x in range(1, c + 1):
		prev_y_max = 0
		for i in range(4):
			prev_y_max = max(dp[i][y - 1][x], prev_y_max)
		dp[0][y][x] = max(prev_y_max, dp[0][y][x - 1])
		if (y, x) in v_dict:
			v = v_dict[y, x]
			dp[1][y][x] = max(prev_y_max + v, dp[0][y][x - 1] + v, dp[1][y][x - 1])
			dp[2][y][x] = max(dp[1][y][x - 1] + v, dp[2][y][x - 1])
			dp[3][y][x] = max(dp[2][y][x - 1] + v, dp[3][y][x - 1])
		else:
			for i in range(1, 4):
				dp[i][y][x] = dp[i][y][x - 1]
ans = 0
for i in range(4):
	ans = max(dp[i][r][c], ans)
print(ans)


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


import sys

def main():
	input = sys.stdin.readline
	(r, c, k) = map(int, input().split())
	items = [[0] * (c + 1) for _ in range(r + 1)]
	for _ in range(k):
		(i, j, v) = map(int, input().split())
		items[i][j] = v
	dp = [[[0] * (c + 1) for _ in range(r + 1)] for _ in range(4)]
	for i in range(1, r + 1):
		for j in range(1, c + 1):
			for m in range(4):
				dp[m][i][j] = max(dp[3][i - 1][j], dp[m][i][j - 1])
			if items[i][j] > 0:
				for m in [2, 1, 0]:
					dp[m + 1][i][j] = max(dp[m + 1][i][j], dp[m][i][j] + items[i][j])
	print(dp[3][r][c])
main()


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(1e+17)
	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()


max2 = lambda x, y: x if x > y else y
min2 = lambda x, y: x if x < y else y
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

def solve(R, C, rcv):
	rows = [list() for _ in range(R)]
	for (r, c, v) in rcv:
		rows[r - 1].append((c - 1, v))
	dp = [0] * C
	for row in rows:
		row.sort()
		row.append((C, 0))
		ri = 0
		(c, v) = row[ri]
		t1 = 0
		t2 = 0
		t3 = 0
		for j in range(C):
			if c == j:
				t3 = max2(t2 + v, t3)
				t2 = max2(t1 + v, t2)
				t1 = max2(dp[j] + v, t1)
				ri += 1
				(c, v) = row[ri]
			dp[j] = max(t3, t2, t1, dp[j])
	return dp[-1]
(R, C, K) = map(int, readline().split())
m = map(int, read().split())
print(solve(R, C, zip(m, m, m)))


f = lambda : map(int, input().split())
g = range
(R, C, K) = f()
a = [[0] * (R + 1) for _ in g(C + 1)]
for _ in g(K):
	(r, c, v) = f()
	a[c][r] = v
dp = [[0] * 4 for _ in g(R + 1)]
for i in g(1, C + 1):
	for j in g(1, R + 1):
		t = a[i][j]
		if t:
			for k in [3, 2, 1]:
				dp[j][k] = max(dp[j][k], dp[j][k - 1] + t)
			dp[j][1] = max(dp[j][1], max(dp[j - 1]) + t)
		dp[j][0] = max(dp[j][0], max(dp[j - 1]))
print(max(dp[R]))


(r, c, k) = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(k)]
dp = [[[0 for _ in range(c + 1)] for _ in range(r + 1)] for _ in range(5)]
for (x, y, z) in a:
	dp[4][x][y] = z
for i in range(1, r + 1):
	for j in range(1, c + 1):
		v = dp[4][i][j]
		dp[0][i][j] = max(dp[0][i][j - 1], dp[0][i - 1][j], dp[1][i - 1][j], dp[2][i - 1][j], dp[3][i - 1][j])
		dp[1][i][j] = max(dp[1][i][j - 1], dp[0][i][j - 1] + v, dp[0][i - 1][j] + v, dp[1][i - 1][j] + v, dp[2][i - 1][j] + v, dp[3][i - 1][j] + v)
		dp[2][i][j] = max(dp[2][i][j - 1], dp[1][i][j - 1] + v)
		dp[3][i][j] = max(dp[3][i][j - 1], dp[2][i][j - 1] + v)
print(max([dp[i][r][c] for i in range(4)]))


import sys
input = sys.stdin.buffer.readline
(H, W, K) = map(int, input().split())
B = {}
for _ in range(K):
	(r, c, v) = map(int, input().split())
	B[r, c] = v
dp = [[0] * 4 for _ in range(W + 1)]
for i in range(1, H + 1):
	for j in range(1, W + 1):
		if (i, j) in B:
			v = B[i, j]
			dp[j][0] = max(dp[j - 1][0], dp[j][0], dp[j][1], dp[j][2], dp[j][3])
			dp[j][1] = max(dp[j - 1][1], dp[j][0] + v)
			dp[j][2] = max(dp[j - 1][2], dp[j - 1][1] + v)
			dp[j][3] = max(dp[j - 1][3], dp[j - 1][2] + v)
		else:
			dp[j][0] = max(dp[j - 1][0], dp[j][0], dp[j][1], dp[j][2], dp[j][3])
			dp[j][1] = dp[j - 1][1]
			dp[j][2] = dp[j - 1][2]
			dp[j][3] = dp[j - 1][3]
print(max(dp[-1]))


from sys import stdin
readline = stdin.readline
(R, C, K) = map(int, readline().split())
goods = [[0] * C for _ in range(R)]
for _ in range(K):
	(r, c, v) = map(int, readline().split())
	goods[r - 1][c - 1] = v
dp = [0] * (C + 1)
for i in range(R):
	cur = [0] * 4
	cur[0] = dp[0]
	for j in range(C):
		if goods[i][j] != 0:
			for k in range(2, -1, -1):
				cur[k + 1] = max(cur[k + 1], cur[k] + goods[i][j])
		dp[j] = max(cur)
		cur[0] = max(cur[0], dp[j + 1])
print(max(cur))


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


(r, c, k) = map(int, input().split())
item = [[0] * (c + 1) for _ in range(r + 1)]
for _ in range(k):
	(i, j, v) = map(int, input().split())
	item[i][j] = 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)
				if k < 3:
					dp[k + 1][i][j + 1] = max(dp[k + 1][i][j + 1], here + item[i][j + 1])
ans = max((dp[k][-1][-1] for k in range(4)))
print(ans)


ma = lambda : map(int, input().split())
lma = lambda : list(map(int, input().split()))
tma = lambda : tuple(map(int, input().split()))
ni = lambda : int(input())
yn = lambda fl: print('Yes') if fl else print('No')
import collections
import math
import itertools
import heapq as hq
(R, C, K) = ma()
V = [[0 for i in range(R + 1)] for j in range(C + 1)]
for i in range(K):
	(r, c, v) = ma()
	V[c][r] = v
dp_prev = [[0] * 4 for i in range(C + 1)]
dp_nex = [[0] * 4 for i in range(C + 1)]
for r in range(1, R + 1):
	for c in range(1, C + 1):
		v = V[c][r]
		for k in range(4):
			if k == 0:
				dp_nex[c][0] = max(dp_prev[c][3], dp_nex[c - 1][0])
			elif k > 0:
				dp_nex[c][k] = max(dp_nex[c - 1][k], dp_nex[c - 1][k - 1] + v, dp_prev[c][3] + v)
	(dp_prev, dp_nex) = (dp_nex, dp_prev)
print(dp_prev[C][3])


import sys
input = sys.stdin.readline
(R, C, K) = map(int, input().split())
RCV = [tuple(map(int, input().split())) for i in range(K)]
goods = [dict() for _ in range(R)]
for (r, c, v) in RCV:
	(r, c) = (r - 1, c - 1)
	goods[r][c] = v
dp0 = [[0] * 4 for _ in range(C)]
dp1 = [[0] * 4 for _ in range(C)]
if 0 in goods[0]:
	dp1[0][1] = goods[0][0]
for i in range(R):
	for j in range(C):
		if i:
			pre = max(dp0[j])
			dp1[j][0] = pre
			if j in goods[i]:
				dp1[j][1] = pre + goods[i][j]
		if j:
			for k in range(4):
				dp1[j][k] = max(dp1[j][k], dp1[j - 1][k])
			if j in goods[i]:
				for k in reversed(range(3)):
					dp1[j][k + 1] = max(dp1[j][k + 1], dp1[j - 1][k] + goods[i][j])
	dp0 = dp1
	dp1 = [[0] * 4 for _ in range(C)]
print(max(dp0[-1]))


import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
(R, C, K) = map(int, readline().split())
data = [[0] * (C + 1) for _ in range(R + 1)]
for _ in range(K):
	(r, c, k) = map(int, readline().split())
	data[r][c] = k
dp = [0] * (C + 1)
for i in range(1, R + 1):
	di = data[i]
	ndp = [0] * (C + 1)
	kdp = [0] * 4
	for j in range(1, C + 1):
		kdp[0] = max(kdp[0], dp[j])
		for k in range(2, -1, -1):
			kdp[k + 1] = max(kdp[k + 1], kdp[k] + di[j])
		ndp[j] = max(kdp)
	dp = ndp
print(dp[C])


import sys
from decimal import Decimal
import math
from itertools import combinations, product
import bisect
from collections import Counter, deque, defaultdict
MOD = 10 ** 6 + 7
INF = 10 ** 9
PI = 3.141592653589793

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


import sys
input = sys.stdin.buffer.readline
(R, C, K) = map(int, input().split())
RC = [[0] * (C + 1) for _ in range(R + 1)]
for _ in range(K):
	(r, c, v) = map(int, input().split())
	RC[r - 1][c - 1] = v
dp = [[[0] * (C + 1) for i in range(R + 1)] for j in range(4)]
dp[1][0][0] = RC[0][0]
for r in range(R):
	for c in range(C):
		for i in range(4):
			dp[i][r][c + 1] = max(dp[i][r][c], dp[i][r][c + 1])
			if i <= 2:
				dp[i + 1][r][c + 1] = max(dp[i][r][c] + RC[r][c + 1], dp[i + 1][r][c + 1])
			dp[0][r + 1][c] = max(dp[i][r][c], dp[0][r + 1][c])
		dp[1][r + 1][c] = max(dp[1][r + 1][c], dp[0][r + 1][c] + RC[r + 1][c])
print(max(dp[0][-2][-2], dp[1][-2][-2], dp[2][-2][-2], dp[3][-2][-2]))


import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
(R, C, K) = map(int, readline().split())
V = [[0] * (C + 1) for _ in range(R + 1)]
for i in range(K):
	(r, c, v) = map(int, readline().split())
	V[r][c] = v
dp = [0] * (C + 1)
dp[0] = 0
for i in range(1, R + 1):
	ndp = [0] * (C + 1)
	row = V[i]
	ldp = [0] * 4
	for j in range(1, C + 1):
		ldp[0] = dp[j]
		for k in range(2, -1, -1):
			ldp[k + 1] = max(ldp[k + 1], ldp[k] + row[j])
		ndp[j] = max(ldp)
	dp = ndp
print(dp[C])


(r, c, k) = map(int, input().split())
lst = [[0] * (c + 1) for i in range(r + 1)]
for i in range(k):
	(s, t, u) = map(int, input().split())
	lst[s][t] = u
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):
		dp1[i][j] = max(dp1[i][j - 1], dp1[i - 1][j] + lst[i][j], dp2[i - 1][j] + lst[i][j], dp3[i - 1][j] + lst[i][j])
		dp2[i][j] = max(dp2[i][j - 1], dp1[i][j - 1] + lst[i][j])
		dp3[i][j] = max(dp3[i][j - 1], dp2[i][j - 1] + lst[i][j])
print(max(dp1[-1][-1], dp2[-1][-1], dp3[-1][-1], 0))


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


import sys

def main():
	input = sys.stdin.readline
	(R, C, k) = map(int, input().split())
	s = [[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())
		s[r][c] = v
	for i in range(R):
		for j in range(C):
			m = max(dp[0][i][j + 1], dp[1][i][j + 1], dp[2][i][j + 1], dp[3][i][j + 1])
			for k in range(4):
				if k == 0:
					dp[k][i + 1][j + 1] = max(dp[k][i + 1][j], m)
				else:
					dp[k][i + 1][j + 1] = max(dp[k][i + 1][j], dp[k - 1][i + 1][j] + s[i + 1][j + 1])
			dp[1][i + 1][j + 1] = max(dp[1][i + 1][j + 1], s[i + 1][j + 1] + m)
	print(max(dp[0][R][C], dp[1][R][C], dp[2][R][C], dp[3][R][C]))
main()


(R, C, K) = map(int, input().split(' '))
original = [[0] * (C + 1) for i in range(R + 1)]
for _ in range(K):
	(r, c, v) = map(int, input().split(' '))
	original[r][c] = v
d1 = [[0] * (C + 1) for i in range(R + 1)]
d2 = [[0] * (C + 1) for i in range(R + 1)]
d3 = [[0] * (C + 1) for i in range(R + 1)]
for i in range(1, R + 1):
	for j in range(1, C + 1):
		curr = original[i][j]
		d1[i][j] = max(d1[i - 1][j] + curr, d2[i - 1][j] + curr, d3[i - 1][j] + curr, d1[i][j - 1], curr)
		d2[i][j] = max(d2[i][j - 1], d1[i][j - 1] + curr)
		d3[i][j] = max(d3[i][j - 1], d2[i][j - 1] + curr)
print(max(d1[-1][-1], d2[-1][-1], d3[-1][-1]))


(r, c, k) = map(int, input().split())
itm = [[0] * c for _ in range(r)]
for i in range(k):
	(ri, ci, vi) = map(int, input().split())
	itm[ri - 1][ci - 1] = vi
dp0 = [[0] * 4 for c_ in range(3005)]
dp1 = [[0] * 4 for c_ in range(3005)]
for i in range(r):
	for j in range(c):
		nowv = itm[i][j]
		dp0[j][3] = max(dp0[j][3], dp0[j][2] + nowv)
		dp0[j][2] = max(dp0[j][2], dp0[j][1] + nowv)
		dp0[j][1] = max(dp0[j][1], dp0[j][0] + nowv)
		dp0[j + 1][0] = max(dp0[j + 1][0], dp0[j][0])
		dp0[j + 1][1] = max(dp0[j + 1][1], dp0[j][1])
		dp0[j + 1][2] = max(dp0[j + 1][2], dp0[j][2])
		dp0[j + 1][3] = max(dp0[j + 1][3], dp0[j][3])
		dp1[j][0] = max(dp1[j][0], max(dp0[j]))
	dp0 = dp1.copy()
print(max(dp1[c - 1]))


(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] = dp[1][j][0] + bord[i][j]
		for x in range(1, 4):
			dp[1][j][x] = max(dp[1][j][x], dp[1][j - 1][x], dp[1][j - 1][x - 1] + bord[i][j])
	dp[0] = dp[1][:]
print(max(dp[1][c - 1]))


(R, C, K) = map(int, input().split())
V = [[0] * (C + 1) for _ in range(R + 1)]
dp1 = [[0, 0, 0, 0] for _ in range(C + 1)]
for _ in range(K):
	(r, c, v) = map(int, input().split())
	V[r][c] = v
for r in range(1, R + 1):
	dp0 = dp1
	dp1 = [[0, 0, 0, 0] for _ in range(C + 1)]
	for c in range(1, C + 1):
		v = V[r][c]
		dprc = dp1[c]
		dprcL = dp1[c - 1]
		if v == 0:
			dprc[0] = max(max(dp0[c]), dprcL[0])
			for n in range(1, 4):
				dprc[n] = dprcL[n]
		else:
			maxT = max(dp0[c])
			dprc[0] = max(maxT, dprcL[0])
			dprc[1] = max(maxT + v, dprcL[0] + v, dprcL[1])
			dprc[2] = max(dprcL[1] + v, dprcL[2])
			dprc[3] = max(dprcL[2] + v, dprcL[3])
print(max(dp1[C]))


import sys
input = lambda : sys.stdin.readline().rstrip()
(r, c, k) = map(int, input().split())
pt = [[0 for _ in range(c + 5)] for _ in range(r + 5)]
for i in range(k):
	(r1, c1, v) = map(int, input().split())
	pt[r1][c1] = v
memo = [[0] * 4 for _ in range(c + 1)]
prev = [[0] * 4 for _ in range(c + 1)]
for i in range(1, r + 1):
	(memo, prev) = (prev, memo)
	for j in range(1, c + 1):
		V = pt[i][j]
		memo[j][0] = max(prev[j][3], memo[j - 1][0])
		memo[j][1] = max(memo[j][0] + V, memo[j - 1][1])
		memo[j][2] = max(memo[j][1], memo[j - 1][1] + V, memo[j - 1][2])
		memo[j][3] = max(memo[j][2], memo[j - 1][2] + V, memo[j - 1][3])
print(memo[-1][3])


import sys
readline = sys.stdin.readline
read = sys.stdin.read
(h, w, k, *hwk) = map(int, read().split())
it = iter(hwk)
b = [[0] * w for _ in range(h + 1)]
for (hi, wi, ki) in zip(it, it, it):
	b[hi - 1][wi - 1] = ki
dp = [[0] * 4 for _ in range(w)]
for i in range(h):
	ndp = [[0] * 4 for _ in range(w)]
	for j in range(w):
		if j != 0:
			ndp[j] = ndp[j - 1][:]
		ndp[j][0] = max(ndp[j][0], max(dp[j]))
		for k in range(3, 0, -1):
			ndp[j][k] = max(ndp[j][k], ndp[j][k - 1] + b[i][j])
	dp = ndp
print(max(dp[-1]))


(r, c, k) = map(int, input().split())
items = [[0] * (c + 1) for _ in range(r + 1)]
for _ in range(k):
	(R, C, V) = map(int, input().split())
	items[R][C] = V
dp0 = [[0] * (c + 1) for _ in range(r + 1)]
dp1 = [[0] * (c + 1) for _ in range(r + 1)]
dp2 = [[0] * (c + 1) for _ in range(r + 1)]
dp3 = [[0] * (c + 1) for _ in range(r + 1)]
for i in range(1, r + 1):
	for j in range(1, c + 1):
		dp0[i][j] = max(dp0[i][j - 1], dp0[i - 1][j], dp1[i - 1][j], dp2[i - 1][j], dp3[i - 1][j])
		dp1[i][j] = max(dp1[i][j - 1], dp0[i - 1][j] + items[i][j], dp1[i - 1][j] + items[i][j], dp2[i - 1][j] + items[i][j], dp3[i - 1][j] + items[i][j], dp0[i][j - 1] + items[i][j])
		dp2[i][j] = max(dp2[i][j - 1], dp1[i][j - 1] + items[i][j])
		dp3[i][j] = max(dp3[i][j - 1], dp2[i][j - 1] + items[i][j])
ans = max(dp0[r][c], dp1[r][c], dp2[r][c], dp3[r][c])
print(ans)


(R, C, K) = map(int, input().split())
RCV = [list(map(int, input().split())) for _ in [0] * K]
V = [[0] * (C + 1) for _ in [0] * (R + 1)]
for (r, c, v) in RCV:
	V[r][c] = v
ans = [[[0] * (C + 1) for _ in [0] * (R + 1)] for _ in [0] * 4]
for r in range(1, R + 1):
	for c in range(C + 1):
		ans[0][r][c] = max(ans[0][r - 1][c], ans[1][r - 1][c], ans[2][r - 1][c], ans[3][r - 1][c])
	i = 1
	for c in range(1, C + 1):
		ans[i][r][c] = max(ans[i][r][c], ans[i][r][c - 1], ans[i - 1][r][c] + V[r][c])
	for i in range(2, 4):
		for c in range(1, C + 1):
			ans[i][r][c] = max(ans[i][r][c], ans[i][r][c - 1], ans[i - 1][r][c - 1] + V[r][c])
out = max(ans[0][-1][-1], ans[1][-1][-1], ans[2][-1][-1], ans[3][-1][-1])
print(out)


(h, w, k) = map(int, input().split())
dp = [[[0] * (w + 2) for _ in range(h + 2)] for _ in range(4)]
f = [[0] * (w + 1) for _ in range(h + 1)]
for _ in range(k):
	(r, c, v) = map(int, input().split())
	f[r][c] = v
for i in range(1, h + 1):
	for j in range(1, w + 1):
		for k in range(3, -1, -1):
			if k:
				dp[k][i][j] = max(dp[k][i][j], dp[k - 1][i][j] + f[i][j])
			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])
print(max((dp[k][h][w] for k in range(4))))


from collections import defaultdict
import sys
input = sys.stdin.readline
(r, c, k) = map(int, input().split())
l = [0] * ((r + 1) * (c + 1))
for i in range(k):
	(a1, a2, a3) = 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]))


(R, C, K) = map(int, input().split())
m = [[0] * (C + 1) for _ in range(R + 1)]
for _ in range(K):
	(r, c, v) = map(int, input().split())
	m[r][c] = v
d = [[0] * 4 for _ in range(R + 1)]
for j in range(1, C + 1):
	for i in range(1, R + 1):
		t = m[i][j]
		if t > 0:
			d[i][3] = max(d[i][3], d[i][2] + t)
			d[i][2] = max(d[i][2], d[i][1] + t)
			d[i][1] = max(d[i][1], d[i][0] + t, max(d[i - 1]) + t)
			d[i][0] = max(d[i][0], max(d[i - 1]))
		else:
			d[i][0] = max(d[i][0], max(d[i - 1]))
print(max(d[R]))


def main():
	(R, C, K) = map(int, input().split())
	S = [[0] * (C + 1) for _ in range(R + 1)]
	for i in range(K):
		(r, c, v) = map(int, input().split())
		S[r][c] = v
	dp = [[[0] * (C + 1) for _ in range(R + 1)] for _ in range(4)]
	for i in range(1, R + 1):
		for j in range(1, C + 1):
			V = S[i][j]
			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] + V)
				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] + V)
	ans = 0
	for k in range(4):
		ans = max(ans, dp[k][R][C])
	print(ans)
main()


def main():
	import sys
	input = sys.stdin.readline
	(r, c, k) = map(int, input().split())
	b = [[0 for _ in range(c)] for _ in range(r)]
	for i in range(k):
		(y, x, v) = map(int, input().split())
		y -= 1
		x -= 1
		b[y][x] = v
	dp = [[0 for _ in range(4)] for _ in range(c + 1)]
	for i in range(r):
		for j in range(c):
			for l in range(2, -1, -1):
				dp[j][l + 1] = max(dp[j][l] + b[i][j], dp[j][l + 1])
			for l in range(4):
				dp[j + 1][l] = max(dp[j][l], dp[j + 1][l])
				dp[j][0] = max(dp[j][l], dp[j][0])
	ans = 0
	for i in range(4):
		ans = max(dp[c - 1][i], ans)
	print(ans)
main()


import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
(r, c, k) = map(int, readline().split())
data = list(map(int, read().split()))
d = dict()
it = iter(data)
for (ri, ci, vi) in zip(it, it, it):
	d[(ri - 1) * 5000 + (ci - 1)] = vi
dp_max = [0] * c
for i in range(r):
	dp = [0] * 4
	for j in range(c):
		dp[0] = max(dp[0], dp_max[j])
		if i * 5000 + j in d:
			ci = d[i * 5000 + j]
			for k in range(3, 0, -1):
				dp[k] = max(dp[k], dp[k - 1] + ci)
		dp_max[j] = max(dp)
print(dp_max[-1])


import sys
input = sys.stdin.readline

def solve():
	(R, C, K) = map(int, input().split())
	item = [[0] * C for _ in range(R)]
	for i in range(K):
		(r, c, v) = map(int, input().split())
		item[r - 1][c - 1] = v
	dp = [[[0] * (C + 1) for _ in range(R + 1)] for _ in range(4)]
	for i in range(1, R + 1):
		for j in range(1, C + 1):
			for k in range(4):
				dp[k][i][j] = dp[k][i][j - 1]
			dp[0][i][j] = max(dp[0][i][j], dp[-1][i - 1][j])
			if item[i - 1][j - 1] > 0:
				dp[1][i][j] = max(dp[1][i][j], dp[-1][i - 1][j] + item[i - 1][j - 1])
				for k in range(1, 4):
					dp[k][i][j] = max(dp[k][i][j], dp[k - 1][i][j - 1] + item[i - 1][j - 1])
			for k in range(1, 4):
				dp[k][i][j] = max(dp[k - 1][i][j], dp[k][i][j])
	ans = 0
	for k in range(4):
		ans = max(ans, dp[k][-1][-1])
	return ans
print(solve())


(R, C, K) = map(int, input().split())
g = [[-float('inf')] * C for _ in range(R)]
for i in range(K):
	(r, c, k) = map(int, input().split())
	r -= 1
	c -= 1
	g[r][c] = k
dp = [[[0] * (C + 1) for _ in range(R + 1)] for _ in range(4)]
for r in range(R):
	for c in range(C):
		for k in range(2, -1, -1):
			dp[k + 1][r][c] = max(dp[k + 1][r][c], dp[k][r][c] + g[r][c])
		for k in range(4):
			dp[0][r + 1][c] = max(dp[0][r + 1][c], dp[k][r][c])
			dp[k][r][c + 1] = max(dp[k][r][c + 1], dp[k][r][c])
ans = 0
for i in range(4):
	ans = max(dp[i][R - 1][C - 1], ans)
print(ans)


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


import sys
input = sys.stdin.readline
(R, C, k) = map(int, input().split())
A = [[0] * C for i in range(R)]
for i in range(k):
	(r, c, v) = 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]))


import sys
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7
input = lambda : sys.stdin.readline().rstrip()
YesNo = lambda b: bool([print('Yes')] if b else print('No'))
YESNO = lambda b: bool([print('YES')] if b else print('NO'))
int1 = lambda x: int(x) - 1
(R, C, K) = map(int, input().split())
V = [[0] * C for _ in range(R)]
for i in range(K):
	(r, c, v) = map(int, input().split())
	r -= 1
	c -= 1
	V[r][c] = v
dp = [[0] * 4 for _ in range(C)]
prev_dp = [[0] * 4 for _ in range(C)]
for y in range(R):
	for x in range(C):
		for i in range(2, -1, -1):
			dp[x][i + 1] = max(dp[x][i + 1], dp[x][i] + V[y][x])
		if x < C - 1:
			for i in range(3, -1, -1):
				dp[x + 1][i] = max(dp[x + 1][i], dp[x][i])
	if y + 1 < R:
		prev_dp = dp
		dp = [[0] * 4 for _ in range(C)]
		for x in range(C):
			dp[x][0] = max(prev_dp[x])
print(max(dp[-1]))


(R, C, K) = 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):
	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]
			for i in range(3)[::-1]:
				nelm[i + 1] = max(elm[i + 1], elm[i] + value)
			elm = nelm
		ndp[c] = max(elm)
	dp = ndp
print(dp[-1])


(R, C, K) = map(int, input().split())
M = [[0 for i in range(C)] for i in range(R)]
for i in range(K):
	(r, c, v) = map(int, input().split())
	r -= 1
	c -= 1
	M[r][c] = v
dp0 = [[0 for j in range(C)] for i in range(R)]
dp1 = [[0 for j in range(C)] for i in range(R)]
dp2 = [[0 for j in range(C)] for i in range(R)]
dp3 = [[0 for j in range(C)] for i in range(R)]
dp1[0][0] += M[0][0]
for r in range(R):
	for c in range(C):
		if 0 < r:
			dp1[r][c] = max(max(dp1[r - 1][c], dp2[r - 1][c], dp3[r - 1][c]) + M[r][c], dp1[r][c])
			dp0[r][c] = max(max(dp1[r - 1][c], dp2[r - 1][c], dp3[r - 1][c]), dp0[r][c])
		if 0 < c:
			dp3[r][c] = max(dp2[r][c - 1] + M[r][c], dp3[r][c], dp3[r][c - 1])
			dp2[r][c] = max(dp1[r][c - 1] + M[r][c], dp2[r][c], dp2[r][c - 1])
			dp1[r][c] = max(dp0[r][c - 1] + M[r][c], dp1[r][c], dp1[r][c - 1])
			dp0[r][c] = max(dp0[r][c - 1], dp0[r][c])
print(max(dp1[-1][-1], dp2[-1][-1], dp3[-1][-1]))


def pri(x):
	for item in x:
		print(item)
(r, c, k) = map(int, input().split())
fuck = [list(map(int, input().split())) for _ in range(k)]
rck = [[0] * (c + 1) for _ in range(r + 1)]
for [rr, cc, kk] in fuck:
	rck[rr][cc] = kk
dp = [[0] * 4 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 - 1][0], dp[x][0], dp[x][1], dp[x][2], dp[x][3])
		dp[x][1] = max(dp[x][0] + rck[y][x], dp[x][1], dp[x - 1][1])
		dp[x][2] = max(dp[x - 1][1] + rck[y][x], dp[x][2], dp[x - 1][2], dp[x][1])
		dp[x][3] = max(dp[x - 1][2] + rck[y][x], dp[x][3], dp[x - 1][3], dp[x][2])
print(max(dp[-1]))


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


import sys
input = sys.stdin.readline
(R, C, k) = map(int, input().split())
xs = [[0] * C for _ in range(R)]
for _ in range(k):
	(r, c, v) = map(int, input().split())
	xs[r - 1][c - 1] = v
dp = [[[0] * (C + 1) for _ in range(R + 1)] for _ in range(4)]
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] + xs[i][j])
		for k in range(4):
			dp[k][i][j + 1] = max(dp[k][i][j + 1], dp[k][i][j])
			dp[0][i + 1][j] = max(dp[0][i + 1][j], dp[k][i][j])
ans = 0
for k in range(4):
	ans = max(ans, dp[k][R - 1][C - 1])
print(ans)


(R, C, K) = map(int, input().split())
rcv = [list(map(int, input().split())) for _ in range(K)]
board = [[0] * (C + 1) for _ in range(R + 1)]
for (r, c, v) in rcv:
	board[r][c] = v
dp = [[[0] * (C + 1) for _ in range(R + 1)] for _ in range(4)]
for r in range(1, R + 1):
	for c in range(1, C + 1):
		v = board[r][c]
		for i in range(4):
			dp[0][r][c] = max(dp[0][r][c], dp[i][r - 1][c])
			dp[1][r][c] = max(dp[1][r][c], dp[i][r - 1][c] + v)
			dp[i][r][c] = max(dp[i][r][c], dp[i][r][c - 1])
			if i > 0:
				dp[i][r][c] = max(dp[i][r][c], dp[i - 1][r][c - 1] + v)
ans = 0
for i in range(4):
	ans = max(ans, dp[i][R][C])
print(ans)


def resolve():
	(R, C, K) = map(int, input().split())
	G = [[0] * (C + 1) for _ in range(R + 1)]
	for _ in range(K):
		(r, c, v) = map(int, input().split())
		G[r][c] = v
	DP1 = [0 for _ in range(C + 1)]
	DP2 = [0 for _ in range(C + 1)]
	DP3 = [0 for _ in range(C + 1)]
	for r in range(1, R + 1):
		for c in range(1, C + 1):
			mid = DP3[c] + G[r][c]
			DP3[c] = max(DP3[c - 1], mid, DP2[c - 1] + G[r][c])
			DP2[c] = max(DP2[c - 1], mid, DP1[c - 1] + G[r][c])
			DP1[c] = max(DP1[c - 1], mid)
	print(DP3[C])
resolve()


(R, C, K) = map(int, input().split())
points_dict = dict()
for _ in range(K):
	(r, c, v) = map(int, input().split())
	points_dict[r * 30000 + c] = v
dp = [[[0] * (C + 1) for _ in range(R + 1)] for _ in range(4)]
index = 0
for i in range(1, R + 1):
	for j in range(1, C + 1):
		for k in range(4):
			if dp[0][i][j] < dp[k][i - 1][j]:
				dp[0][i][j] = dp[k][i - 1][j]
			if dp[k][i][j] < dp[k][i][j - 1]:
				dp[k][i][j] = dp[k][i][j - 1]
		if i * 30000 + j in points_dict:
			v = points_dict[i * 30000 + j]
			for k in range(3, 0, -1):
				if dp[k][i][j] < dp[k - 1][i][j] + v:
					dp[k][i][j] = dp[k - 1][i][j] + v
print(max((dp[i][R][C] for i in range(4))))


import sys
input = sys.stdin.buffer.readline

def main():
	(R, C, K) = map(int, input().split())
	State = [[0] * R for _ in range(C)]
	for _ in range(K):
		(r, c, v) = map(int, input().split())
		State[c - 1][r - 1] += v
	dp = [[0] * 4 for _ in range(C + 1)]
	for r in range(R):
		ndp = [[0] * 4 for _ in range(C + 1)]
		for c in range(C):
			ndp[c + 1][0] = max(ndp[c + 1][0], max(dp[c + 1]))
			ndp[c + 1][1] = ndp[c + 1][0] + State[c][r]
			for n in range(4):
				if ndp[c][n] > ndp[c + 1][n]:
					ndp[c + 1][n] = ndp[c][n]
				if n < 3 and ndp[c][n] + State[c][r] > ndp[c + 1][n + 1]:
					ndp[c + 1][n + 1] = ndp[c][n] + State[c][r]
		dp = ndp
	print(max(dp[C]))
main()


(R, C, K) = map(int, input().split())
Items = [[0] * (C + 1) for _ in range(R + 1)]
for _ in range(K):
	(r, c, v) = 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]))


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


def main(R, C, K, V):
	dp = [0] * (4 * R * C)
	dp[1 + 4 * 0 + 4 * C * 0] = V[0][0]
	for k in range(4 * R * C):
		n = k % 4
		j = k // 4 % C
		i = k // (4 * C)
		if n != 0:
			if i != 0 and n == 1:
				dp[k] = max(dp[k - 4 * C - n:k - 4 * C - n + 4]) + V[i][j]
			if j != 0:
				dp[k] = max(dp[k], dp[k - 4], dp[k - 5] + V[i][j])
		if n == 0:
			if i != 0:
				dp[k] = max(dp[k - 4 * C - n:k - 4 * C - n + 4])
	print(max(dp[-5:-1]))
(R, C, K) = map(int, input().split())
C += 1
rcv = [list(map(int, input().split())) for _ in range(K)]
V = [[0] * C for _ in range(R)]
for i in range(K):
	(r, c, v) = rcv[i]
	r -= 1
	c -= 1
	V[r][c] = v
main(R, C, K, V)


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


(R, C, K) = map(int, input().split())
value = [[0] * (C + 1) for i in range(R + 1)]
for i in range(K):
	(r, c, v) = map(int, input().split())
	value[r][c] = 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 = value[i][j]
		a = DP0[i][j - 1]
		b = DP1[i][j - 1]
		c = DP1[i - 1][j]
		d = DP2[i - 1][j]
		e = DP3[i - 1][j]
		f = DP2[i][j - 1]
		DP0[i][j] = max(a, c, d, e)
		DP1[i][j] = max(DP0[i - 1][j] + v, c + v, d + v, e + v, b, a + v)
		DP2[i][j] = max(b + v, f)
		DP3[i][j] = max(f + v, DP3[i][j - 1])
print(max(DP0[R][C], DP1[R][C], DP2[R][C], DP3[R][C]))


import sys
from pprint import pprint
(R, C, K) = map(int, input().split())
grid = [[0] * C for _ in range(R + 1)]
for _ in range(K):
	(r, c, v) = map(int, input().split())
	grid[r][c - 1] = v
for i in range(1, R + 1):
	cell = [0] * 4
	for j in range(C):
		cell[0] = max(cell[0], grid[i - 1][j])
		for k in range(2, -1, -1):
			cell[k + 1] = max(cell[k + 1], cell[k] + grid[i][j])
		grid[i][j] = max(cell)
print(grid[-1][-1])


def main():
	(R, C, K) = map(int, input().split())
	V = {}
	for _ in range(K):
		(r, c, v) = map(int, input().split())
		V[r - 1, c - 1] = v
	dp = [(0, 0, 0, 0) for _ in range(C)]
	for r in range(R):
		(p0, p1, p2, p3) = (0, 0, 0, 0)
		for c in range(C):
			m = max(dp[c])
			if (r, c) in V:
				v = V[r, c]
				(n0, n1, n2, n3) = (max(m, p0), max(p1, max(p0, m) + v), max(p2, p1 + v), max(p3, p2 + v))
			else:
				(n0, n1, n2, n3) = (max(m, p0), p1, p2, p3)
			dp[c] = (n0, n1, n2, n3)
			(p0, p1, p2, p3) = (n0, n1, n2, n3)
	return max(dp[-1])
print(main())


(R, C, K) = map(int, input().split())
J = [0] * K
for i in range(K):
	J[i] = list(map(int, input().split()))
DP1 = [[0] * (C + 2) for i in range(R + 2)]
DP2 = [[0] * (C + 2) for i in range(R + 2)]
DP3 = [[0] * (C + 2) for i in range(R + 2)]
MAP = [[0] * C for i in range(R)]
for (x, y, v) in J:
	MAP[x - 1][y - 1] = v
for i in range(R):
	for j in range(C):
		DP1[i][j] = max(DP1[i][j - 1], DP1[i - 1][j] + MAP[i][j], DP2[i - 1][j] + MAP[i][j], DP3[i - 1][j] + MAP[i][j])
		DP2[i][j] = max(DP2[i][j - 1], DP1[i][j - 1] + MAP[i][j])
		DP3[i][j] = max(DP3[i][j - 1], DP2[i][j - 1] + MAP[i][j])
ANS = 0
for i in range(R):
	for j in range(C):
		ANS = max(ANS, DP1[i][j], DP2[i][j], DP3[i][j])
print(ANS)


(R, C, K) = map(int, input().split())
A = [[0] * 4 for _ in range(C + 1)]
B = [[-1] * (C + 1) for _ in range(R + 1)]
for k in range(K):
	(r, c, v) = map(int, input().split())
	B[r][c] = v
for r in range(1, R + 1):
	D = A[:]
	for c in range(1, C + 1):
		if B[r][c] == -1:
			A[c][0] = max(A[c - 1][0], max(D[c]))
			A[c][1] = max(A[c - 1][1], max(D[c]))
			A[c][2] = max(A[c - 1][2], max(D[c]))
			A[c][3] = max(A[c - 1][3], max(D[c]))
		else:
			A[c][0] = max(A[c - 1][0], max(D[c]))
			A[c][1] = max(A[c - 1][1], A[c - 1][0] + B[r][c], max(D[c]) + B[r][c])
			A[c][2] = max(A[c - 1][2], A[c - 1][1] + B[r][c])
			A[c][3] = max(A[c - 1][3], A[c - 1][2] + B[r][c])
print(max(A[-1]))


import sys
input = sys.stdin.readline
(r, c, k) = map(int, input().split())
v = [[0 for j in range(c)] for i in range(r)]
dp = [[[0 for j in range(c)] for i in range(r)] for k in range(4)]
for i in range(k):
	(ri, ci, vi) = map(int, input().split())
	v[ri - 1][ci - 1] = vi
for i in range(r):
	if i > 0:
		for j in range(c):
			for k in range(4):
				dp[0][i][j] = max(dp[0][i][j], dp[k][i - 1][j])
	for j in range(c):
		if j > 0:
			for k in range(4):
				dp[k][i][j] = max(dp[k][i][j], dp[k][i][j - 1])
		if v[i][j]:
			for k in reversed(range(1, 4)):
				dp[k][i][j] = max(dp[k][i][j], dp[k - 1][i][j] + v[i][j])
ans = 0
for k in range(4):
	ans = max(ans, dp[k][r - 1][c - 1])
print(ans)


(R, C, K) = map(int, input().split())
V = [[0] * (C + 1) for _ in range(R + 1)]
for _ in range(K):
	(r, c, v) = map(int, input().split())
	V[r][c] = v
max_pre = [0] * (C + 1)
for i in range(R + 1):
	now = [[0] * (3 + 1) for _ in range(C + 1)]
	for j in range(C + 1):
		v = V[i][j]
		la = lb = 0
		if j > 0:
			la = now[j - 1][0]
			lb = now[j - 1][1]
			now[j][2] = max(now[j][2], now[j - 1][2], lb + v)
			now[j][3] = max(now[j][3], now[j - 1][3], now[j - 1][2] + v)
		if i > 0:
			now[j][0] = max(now[j][0], max_pre[j], la)
			now[j][1] = max(now[j][1], max_pre[j] + v, la + v, lb)
		max_pre[j] = max(now[j])
print(max(now[C]))


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


def max2(x, y):
	return x if x > y else y
(R, L, K) = map(int, input().split())
V = [[0] * R for _ in range(L)]
for _ in range(K):
	(r, c, v) = map(int, input().split())
	V[c - 1][r - 1] = v
(A, B, C, D) = [[0] * (R + 1) for _ in range(4)]
for i in range(L):
	for j in range(R):
		A[j] = max(A[j - 1], B[j - 1], C[j - 1], D[j - 1])
		v = V[i][j]
		if v != 0:
			(D[j], C[j], B[j]) = (max2(C[j] + v, D[j]), max2(B[j] + v, C[j]), max2(A[j] + v, B[j]))
print(max(A[-2], B[-2], C[-2], D[-2]))


import sys
input = sys.stdin.readline
(H, W, K) = map(int, input().split())
G = [[0] * W for i in range(H)]
for i in range(K):
	(r, c, v) = map(int, input().split())
	(r, c) = (r - 1, c - 1)
	G[r][c] = v
dp = [[[-1] * W for i in range(H)] for i in range(4)]
dp[0][0][0] = 0
if G[0][0] != 0:
	dp[1][0][0] = G[0][0]
for i in range(H):
	for j in range(W):
		m = max((dp[k][i][j] for k in range(4)))
		if i + 1 < H:
			dp[1][i + 1][j] = max(dp[1][i + 1][j], m + G[i + 1][j])
			dp[0][i + 1][j] = max(dp[0][i + 1][j], m)
		if j + 1 < W:
			dp[0][i][j + 1] = 0
			dp[1][i][j + 1] = max(dp[1][i][j + 1], dp[1][i][j], dp[0][i][j] + G[i][j + 1])
			dp[2][i][j + 1] = max(dp[2][i][j + 1], dp[2][i][j], dp[1][i][j] + G[i][j + 1])
			dp[3][i][j + 1] = max(dp[3][i][j + 1], dp[3][i][j], dp[2][i][j] + G[i][j + 1])
ans = max((dp[i][H - 1][W - 1] for i in range(4)))
print(ans)


import sys, queue, math, copy, itertools, bisect, collections, heapq

def main():
	LI = lambda : [int(x) for x in sys.stdin.readline().split()]
	(R, C, K) = LI()
	m = [[0] * (C + 1) for _ in range(R + 1)]
	dp = [[0] * 4 for _ in range(C + 1)]
	for _ in range(K):
		(r, c, v) = LI()
		m[r][c] = v
	for i in range(1, R + 1):
		for j in range(1, C + 1):
			b_max = max(dp[j])
			dp[j][0] = max(dp[j - 1][0], b_max)
			if m[i][j] > 0:
				for k in range(1, 4):
					dp[j][k] = max(dp[j - 1][k], dp[j - 1][k - 1] + m[i][j])
				dp[j][1] = max(dp[j][1], b_max + m[i][j])
			else:
				for k in range(1, 4):
					dp[j][k] = dp[j - 1][k]
	print(max(dp[-1]))
main()


import sys
input = sys.stdin.readline
(R, C, K) = map(int, input().split())
values = [[0] * C for _ in range(R)]
for _ in range(K):
	(r, c, v) = map(int, input().split())
	values[r - 1][c - 1] = v
dp = [[[0 for _ in range(C + 1)] for _ in range(R + 1)] for _ in range(4)]
for r in range(R - 1, -1, -1):
	for c in range(C - 1, -1, -1):
		v = values[r][c]
		for i in range(4):
			if i == 0 or v == 0:
				dp[i][r][c] = max(dp[3][r + 1][c], dp[i][r][c + 1])
			else:
				dp[i][r][c] = max(dp[3][r + 1][c] + v, dp[i][r][c + 1], dp[i - 1][r][c + 1] + v)
print(dp[3][0][0])


(R, C, K) = 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):
	for j in range(1, C + 1):
		dp[j][0] = max(dp[j])
		for k in range(1, 4):
			dp[j][k] = 0
	for j in range(1, C + 1):
		for k in reversed(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]))


(R, C, K) = map(int, input().split())
V = [[0] * (C + 1) for _ in range(R + 1)]
for _ in range(K):
	(r, c, v) = map(int, input().split())
	V[r][c] = v
pre = [[0] * (3 + 1) for _ in range(C + 1)]
for i in range(R + 1):
	now = [[0] * (3 + 1) for _ in range(C + 1)]
	for j in range(C + 1):
		for k in range(3 + 1):
			if i - 1 >= 0:
				now[j][0] = max(now[j][0], pre[j][k])
				now[j][1] = max(now[j][1], pre[j][k] + V[i][j])
			if j - 1 >= 0:
				now[j][k] = max(now[j][k], now[j - 1][k])
				if k - 1 >= 0:
					now[j][k] = max(now[j][k], now[j - 1][k - 1] + V[i][j])
	pre = now
print(max(now[C]))


(R, C, K) = map(int, input().split())
V = [[0] * (R + 1) for _ in range(C + 1)]
for _ in range(K):
	(r, c, v) = map(int, input().split())
	V[c][r] = v
X = [[0] * 4 for _ in range(R + 1)]
for i in range(1, C + 1):
	Vi = V[i]
	for j in range(1, R + 1):
		v = Vi[j]
		Xj = X[j]
		if v:
			Xj[3] = max(Xj[3], Xj[2] + v)
			Xj[2] = max(Xj[2], Xj[1] + v)
			Xj[0] = max(Xj[0], max(X[j - 1]))
			Xj[1] = max(Xj[1], Xj[0] + v)
		else:
			Xj[0] = max(Xj[0], max(X[j - 1]))
print(max(X[R]))


from copy import copy
(C, R, K) = map(int, input().split())
dp = [[0] * (R + 1) for i1 in range(4)]
M = [[0] * R for i in range(C)]
for i in range(K):
	(r, c, v) = map(int, input().split())
	M[r - 1][c - 1] = v
for (i, l) in enumerate(M):
	for num in range(1, 4):
		for j in range(R):
			if num == 1:
				dp[num][j] = max(dp[num][j - 1], dp[num - 1][j - 1] + M[i][j])
			else:
				dp[num][j] = max(dp[num][j - 1], dp[num - 1][j], dp[num - 1][j - 1] + M[i][j])
	dp[0] = dp[-1][1:-1] + [0, dp[-1][0]]
print(dp[-1][-2])


import sys
input = sys.stdin.readline
(r, c, k) = map(int, input().split())
v = [[0 for _ in range(c)] for _ in range(r)]
for i in range(k):
	(rr, cc, vv) = map(int, input().split())
	(rr, cc) = (rr - 1, cc - 1)
	v[rr][cc] = vv
dp = [[0 for _ in range(c + 1)] for _ in range(4)]
for y in range(r):
	tmp = [[0 for _ in range(c + 1)] for _ in range(4)]
	for x in range(c):
		for i in range(2, -1, -1):
			dp[i + 1][x] = max(dp[i + 1][x], dp[i][x] + v[y][x])
		for i in range(4):
			tmp[0][x] = max(tmp[0][x], dp[i][x])
			dp[i][x + 1] = max(dp[i][x + 1], dp[i][x])
	dp = tmp
print(dp[0][c - 1])


(r, c, k) = map(int, input().split())
v = [map(int, input().split()) for _ in range(k)]
sq = [[0 for _ in range(c)] for _ in range(r)]
for (ri, ci, vi) in v:
	sq[ri - 1][ci - 1] = vi
dp = [[[0 for _ in range(c)] for _ in range(4)] for _ in range(2)]
for ri in range(r):
	if 0 < ri:
		for ci in range(c):
			dp[ri % 2][0][ci] = max([dp[1 - ri % 2][i][ci] for i in range(4)])
			for i in range(1, 4):
				dp[ri % 2][i][ci] = 0
	for ci in range(c):
		if 0 < ci:
			for i in range(4):
				dp[ri % 2][i][ci] = max(dp[ri % 2][i][ci], dp[ri % 2][i][ci - 1])
		if 0 < sq[ri][ci]:
			for i in range(2, -1, -1):
				dp[ri % 2][i + 1][ci] = max(dp[ri % 2][i + 1][ci], dp[ri % 2][i][ci] + sq[ri][ci])
ans = max([dp[ri % 2][i][-1] for i in range(4)])
print(ans)


(R, C, K) = map(int, input().split())
inf = float('inf')
v_list = [[0 for _ in range(C)] for _ in range(R)]
for _ in range(K):
	(r, c, v) = map(int, input().split())
	v_list[r - 1][c - 1] = v
dp = [[0, 0, 0, 0] for _ in range(C)]
for r in range(R):
	for c in range(C):
		if c > 0:
			dp[c][0] = max(dp[c])
			dp[c][1] = dp[c - 1][1]
			dp[c][2] = dp[c - 1][2]
			dp[c][3] = dp[c - 1][3]
		else:
			dp[c][0] = max(dp[c])
			dp[c][1] = 0
			dp[c][2] = 0
			dp[c][3] = 0
		if v_list[r][c] > 0:
			v = v_list[r][c]
			dp[c][3] = max(dp[c][2] + v, dp[c][3])
			dp[c][2] = max(dp[c][1] + v, dp[c][2])
			dp[c][1] = max(dp[c][0] + v, dp[c][1])
print(max(dp[-1]))


import sys
sys.setrecursionlimit(500005)
stdin = sys.stdin
ni = lambda : int(ns())
na = lambda : list(map(int, stdin.readline().split()))
ns = lambda : stdin.readline().strip()
(R, C, K) = na()
g = [[0] * C for _ in range(R)]
for i in range(K):
	(r, c, v) = na()
	g[r - 1][c - 1] = v
I = -9999999999999999999
dp = [I] * C
dp[0] = 0
for i in range(R):
	ndp = [I] * C
	row = g[i]
	ldp = [I] * 4
	for j in range(C):
		ldp[0] = max(ldp[0], dp[j])
		for k in range(2, -1, -1):
			ldp[k + 1] = max(ldp[k + 1], ldp[k] + row[j])
		ndp[j] = max(ldp)
	dp = ndp
print(dp[C - 1])


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:
					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) = 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
input = sys.stdin.buffer.readline
(r, c, k) = map(int, input().split())
v = [[0] * (c + 1) for i in range(r + 1)]
for i in range(k):
	(cr, cc, cv) = map(int, input().split())
	v[cr][cc] = cv
dp = [[0] * 4 for _ in range(c + 1)]
last = [[0] * 4 for _ in range(c + 1)]
for cr in range(1, r + 1):
	for cc in range(1, c + 1):
		upper = max(last[cc][0], last[cc][1], last[cc][2], last[cc][3])
		dp[cc][0] = max(upper, dp[cc - 1][0], dp[cc][0])
		dp[cc][1] = max(dp[cc - 1][1], dp[cc - 1][0] + v[cr][cc], upper + v[cr][cc])
		dp[cc][2] = max(dp[cc - 1][2], dp[cc - 1][1] + v[cr][cc])
		dp[cc][3] = max(dp[cc - 1][3], dp[cc - 1][2] + v[cr][cc])
		last = dp
print(max(dp[c]))


def main():
	import sys
	from copy import deepcopy
	input = sys.stdin.readline
	(R, C, K) = [int(x) for x in input().strip().split()]
	G = [[0] * (C + 1) for r in range(R + 1)]
	for k in range(K):
		(r, c, v) = [int(x) for x in input().strip().split()]
		G[r][c] = v
	ans = [[[0] * 4 for _ in range(C + 1)] for _ in range(2)]
	for r in range(1, R + 1):
		for c in range(1, C + 1):
			ans[r % 2][c][0] = max(ans[(r - 1) % 2][c][-1], ans[r % 2][c - 1][0])
			for i in range(1, 4):
				ans[r % 2][c][i] = max(ans[(r - 1) % 2][c][3], ans[r % 2][c - 1][i], ans[(r - 1) % 2][c][3] + G[r][c], ans[r % 2][c - 1][i - 1] + G[r][c])
	print(max(ans[R % 2][-1]))
main()


import sys
input = sys.stdin.readline
(h, w, k) = map(int, input().split())
G = [[0] * w for _ in range(h)]
for _ in range(k):
	(r, c, v) = map(int, input().split())
	r -= 1
	c -= 1
	G[r][c] = v
dp = [[[0] * w for i in range(h)] for j in range(4)]
dp[0][0][0] = 0
dp[1][0][0] = G[0][0]
for i in range(h):
	for j in range(w):
		if j:
			dp[0][i][j] = dp[0][i][j - 1]
			for k in range(1, 4):
				dp[k][i][j] = max(dp[k][i][j], dp[k - 1][i][j - 1] + G[i][j], dp[k][i][j - 1])
		if i:
			dp[0][i][j] = max(dp[0][i][j], max(dp[0][i - 1][j], dp[1][i - 1][j], dp[2][i - 1][j], dp[3][i - 1][j]))
			dp[1][i][j] = max(dp[1][i][j], max(dp[0][i - 1][j], dp[1][i - 1][j], dp[2][i - 1][j], dp[3][i - 1][j]) + G[i][j])
ans = max(dp[0][h - 1][w - 1], dp[1][h - 1][w - 1], dp[2][h - 1][w - 1], dp[3][h - 1][w - 1])
print(ans)


(R, C, K) = 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) = 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]))


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


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

def solve():
	memo = [[0] * 4 for _ in range(C + 1)]
	prev = [[0] * 4 for _ in range(C + 1)]
	for r in range(1, R + 1):
		(prev, memo) = (memo, prev)
		for c in range(1, C + 1):
			v = RC[r - 1][c - 1]
			memo[c][0] = max(prev[c][3], memo[c - 1][0])
			memo[c][1] = max(memo[c][0] + v, memo[c - 1][1])
			memo[c][2] = max(memo[c][1], memo[c - 1][1] + v, memo[c - 1][2])
			memo[c][3] = max(memo[c][2], memo[c - 1][2] + v, memo[c - 1][3])
	return memo[-1][3]
print(solve())


(R, C, K) = map(int, input().split())
dp0 = [[0 for _ in range(C + 1)] for f in range(R + 1)]
dp1 = [[0 for _ in range(C + 1)] for f in range(R + 1)]
dp2 = [[0 for _ in range(C + 1)] for f in range(R + 1)]
dp3 = [[0 for _ in range(C + 1)] for f in range(R + 1)]
vl = [[0 for _ in range(C + 1)] for f in range(R + 1)]
for i in range(K):
	(r, c, v) = map(int, input().split())
	vl[r][c] = v
for i in range(1, R + 1):
	for j in range(1, C + 1):
		dp0[i][j] = max(dp0[i][j], dp0[i - 1][j], dp1[i - 1][j], dp2[i - 1][j], dp3[i - 1][j])
		dp3[i][j] = max(dp3[i][j], dp3[i][j - 1], dp2[i][j - 1] + vl[i][j], dp2[i][j] + vl[i][j])
		dp2[i][j] = max(dp2[i][j], dp2[i][j - 1], dp1[i][j - 1] + vl[i][j], dp1[i][j] + vl[i][j])
		dp1[i][j] = max(dp1[i][j], dp1[i][j - 1], dp0[i][j - 1] + vl[i][j], dp0[i][j] + vl[i][j])
print(max(dp0[R][C], dp1[R][C], dp2[R][C], dp3[R][C]))