Buggy python submission (verdict: Time Limit Exceeded):
import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 1000000007
sys.setrecursionlimit(1000000)
 
R, C, K = rl()
I = [[0]*(C+2) for _ in range(R+2)]
for i in range(K):
	r, c, v = rl()
	I[r][c] = v
 
dp = [[[0]*4 for _ in range(C+2)] for _ in range(R+2)]
 
for i in range(R+1):
	dpi = dp[i]
	dpi2 = dp[i+1]
	for j in range(C+1):
		for m in range(4):
			ni, nj = i, j+1
			dpi[nj][m] = max(dpi[nj][m], dpi[j][m])
			if m < 3:
				dpi[nj][m+1] = max(dpi[nj][m+1], dpi[j][m]+I[ni][nj])
			ni, nj = i+1, j
			dpi2[nj][0] = max(dpi2[nj][0], dpi[j][m])
			dpi2[nj][1] = max(dpi2[nj][1], dpi[j][m]+I[ni][nj])
ans = 0
for m in range(4):
	ans = max(ans, dp[R][C][m])
print(ans)


Fixed submission:
import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 1000000007
sys.setrecursionlimit(1000000)
 
R, C, K = rl()
I = [[0]*(C+2) for _ in range(R+2)]
for i in range(K):
	r, c, v = rl()
	I[r][c] = v
 
dp = [[0]*4 for _ in range(C+2)]
dp2 = [[0]*4 for _ in range(C+2)]
 
for i in range(R+1):
	for j in range(C+1):
		for m in range(4):
			ni, nj = i, j+1
			dp[nj][m] = max(dp[nj][m], dp[j][m])
			if m < 3:
				dp[nj][m+1] = max(dp[nj][m+1], dp[j][m]+I[ni][nj])
			ni, nj = i+1, j
			dp2[nj][0] = max(dp2[nj][0], dp[j][m])
			dp2[nj][1] = max(dp2[nj][1], dp[j][m]+I[ni][nj])
	dp = dp2
	dp2 = [[0]*4 for _ in range(C+2)]
ans = 0
for m in range(4):
	ans = max(ans, dp[C][m])
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 1000000007
sys.setrecursionlimit(1000000)

import numpy as np

R, C, K = rl()
#I = [[0]*(C+2) for _ in range(R+2)]
I = np.zeros((R+2, C+2), dtype=np.int)
for i in range(K):
	r, c, v = rl()
	I[r][c] = v
 
#dp = [[[0 for _ in range(C+2)] for _ in range(R+2)] for _ in range(4)]
dp = np.zeros((4,R+2,C+2), dtype=np.int)

for i in range(R+1):
	for j in range(C+1):
		for m in range(4):
			ni, nj = i, j+1
			dp[m][ni][nj] = max(dp[m][ni][nj], dp[m][i][j])
			if m < 3:
				dp[m+1][ni][nj] = max(dp[m+1][ni][nj], dp[m][i][j]+I[ni][nj])
			ni, nj = i+1, j
			dp[0][ni][nj] = max(dp[0][ni][nj], dp[m][i][j])
			dp[1][ni][nj] = max(dp[1][ni][nj], dp[m][i][j]+I[ni][nj])
ans = 0
for m in range(4):
	ans = max(ans, dp[m][R][C])
print(ans)


Fixed submission:
import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 1000000007
sys.setrecursionlimit(1000000)
 
R, C, K = rl()
I = [[0]*(C+2) for _ in range(R+2)]
for i in range(K):
	r, c, v = rl()
	I[r][c] = v
 
dp = [[0]*4 for _ in range(C+2)]
dp2 = [[0]*4 for _ in range(C+2)]
 
for i in range(R+1):
	for j in range(C+1):
		for m in range(4):
			ni, nj = i, j+1
			dp[nj][m] = max(dp[nj][m], dp[j][m])
			if m < 3:
				dp[nj][m+1] = max(dp[nj][m+1], dp[j][m]+I[ni][nj])
			ni, nj = i+1, j
			dp2[nj][0] = max(dp2[nj][0], dp[j][m])
			dp2[nj][1] = max(dp2[nj][1], dp[j][m]+I[ni][nj])
	dp = dp2
	dp2 = [[0]*4 for _ in range(C+2)]
ans = 0
for m in range(4):
	ans = max(ans, dp[C][m])
print(ans)

Buggy python submission (verdict: Runtime Error):
import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 1000000007
sys.setrecursionlimit(1000000)

import numpy as np

R, C, K = rl()
#I = [[0]*(C+2) for _ in range(R+2)]
I = np.zeros([R+2, C+2], dtype=int)
for i in range(K):
	r, c, v = rl()
	I[r][c] = v
 
#dp = [[[0 for _ in range(C+2)] for _ in range(R+2)] for _ in range(4)]
dp = np.zeros([4,R+2,C+2], dtype=int)

for i in range(R+1):
	for j in range(C+1):
		for m in range(4):
			ni, nj = i, j+1
			dp[m][ni][nj] = max(dp[m][ni][nj], dp[m][i][j])
			if m < 3:
				dp[m+1][ni][nj] = max(dp[m+1][ni][nj], dp[m][i][j]+I[ni][nj])
			ni, nj = i+1, j
			dp[0][ni][nj] = max(dp[0][ni][nj], dp[m][i][j])
			dp[1][ni][nj] = max(dp[1][ni][nj], dp[m][i][j]+I[ni][nj])
ans = 0
for m in range(4):
	ans = max(ans, dp[m][R][C])
print(ans)


Fixed submission:
import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 1000000007
sys.setrecursionlimit(1000000)
 
R, C, K = rl()
I = [[0]*(C+2) for _ in range(R+2)]
for i in range(K):
	r, c, v = rl()
	I[r][c] = v
 
dp = [[0]*4 for _ in range(C+2)]
dp2 = [[0]*4 for _ in range(C+2)]
 
for i in range(R+1):
	for j in range(C+1):
		for m in range(4):
			ni, nj = i, j+1
			dp[nj][m] = max(dp[nj][m], dp[j][m])
			if m < 3:
				dp[nj][m+1] = max(dp[nj][m+1], dp[j][m]+I[ni][nj])
			ni, nj = i+1, j
			dp2[nj][0] = max(dp2[nj][0], dp[j][m])
			dp2[nj][1] = max(dp2[nj][1], dp[j][m]+I[ni][nj])
	dp = dp2
	dp2 = [[0]*4 for _ in range(C+2)]
ans = 0
for m in range(4):
	ans = max(ans, dp[C][m])
print(ans)

Buggy python submission (verdict: Runtime Error):
import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 1000000007
sys.setrecursionlimit(1000000)

import numpy as np

R, C, K = rl()
#I = [[0]*(C+2) for _ in range(R+2)]
I = np.zeros([R+2, C+2], dtype=int)
for i in range(K):
	r, c, v = rl()
	I[r][c] = v
 
#dp = [[[0 for _ in range(C+2)] for _ in range(R+2)] for _ in range(4)]
dp = np.zeros([4,R+2,C+2], dtype=int)

for i in range(R+1):
	for j in range(C+1):
		for m in range(4):
			ni, nj = i, j+1
			dp[m][ni][nj] = max(dp[m][ni][nj], dp[m][i][j])
			if m < 3:
				dp[m+1][ni][nj] = max(dp[m+1][ni][nj], dp[m][i][j]+I[ni][nj])
			ni, nj = i+1, j
			dp[0][ni][nj] = max(dp[0][ni][nj], dp[m][i][j])
			dp[1][ni][nj] = max(dp[1][ni][nj], dp[m][i][j]+I[ni][nj])
ans = 0
for m in range(4):
	ans = max(ans, dp[m][R][C])
print(ans)


Fixed submission:
import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 1000000007
sys.setrecursionlimit(1000000)
 
R, C, K = rl()
I = [[0]*(C+2) for _ in range(R+2)]
for i in range(K):
	r, c, v = rl()
	I[r][c] = v
 
dp = [[0]*4 for _ in range(C+2)]
dp2 = [[0]*4 for _ in range(C+2)]
 
for i in range(R+1):
	for j in range(C+1):
		for m in range(4):
			ni, nj = i, j+1
			dp[nj][m] = max(dp[nj][m], dp[j][m])
			if m < 3:
				dp[nj][m+1] = max(dp[nj][m+1], dp[j][m]+I[ni][nj])
			ni, nj = i+1, j
			dp2[nj][0] = max(dp2[nj][0], dp[j][m])
			dp2[nj][1] = max(dp2[nj][1], dp[j][m]+I[ni][nj])
	dp = dp2
	dp2 = [[0]*4 for _ in range(C+2)]
ans = 0
for m in range(4):
	ans = max(ans, dp[C][m])
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 1000000007
sys.setrecursionlimit(1000000)
 
R, C, K = rl()
I = [[0]*(C+2) for _ in range(R+2)]
for i in range(K):
	r, c, v = rl()
	I[r][c] = v
 
dp = [[[0 for _ in range(C+2)] for _ in range(R+2)] for _ in range(4)]

for i in range(R+1):
	for j in range(C+1):
		for m in range(4):
			ni, nj = i, j+1
			dp[m][ni][nj] = max(dp[m][ni][nj], dp[m][i][j])
			if m < 3:
				dp[m+1][ni][nj] = max(dp[m+1][ni][nj], dp[m][i][j]+I[ni][nj])
			ni, nj = i+1, j
			dp[0][ni][nj] = max(dp[0][ni][nj], dp[m][i][j])
			dp[1][ni][nj] = max(dp[1][ni][nj], dp[m][i][j]+I[ni][nj])
ans = 0
for m in range(4):
	ans = max(ans, dp[m][R][C])
print(ans)


Fixed submission:
import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 1000000007
sys.setrecursionlimit(1000000)
 
R, C, K = rl()
I = [[0]*(C+2) for _ in range(R+2)]
for i in range(K):
	r, c, v = rl()
	I[r][c] = v
 
dp = [[0]*4 for _ in range(C+2)]
dp2 = [[0]*4 for _ in range(C+2)]
 
for i in range(R+1):
	for j in range(C+1):
		for m in range(4):
			ni, nj = i, j+1
			dp[nj][m] = max(dp[nj][m], dp[j][m])
			if m < 3:
				dp[nj][m+1] = max(dp[nj][m+1], dp[j][m]+I[ni][nj])
			ni, nj = i+1, j
			dp2[nj][0] = max(dp2[nj][0], dp[j][m])
			dp2[nj][1] = max(dp2[nj][1], dp[j][m]+I[ni][nj])
	dp = dp2
	dp2 = [[0]*4 for _ in range(C+2)]
ans = 0
for m in range(4):
	ans = max(ans, dp[C][m])
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 1000000007
sys.setrecursionlimit(1000000)

R, C, K = rl()
I = [[0]*(C+2) for _ in range(R+2)]
for i in range(K):
	r, c, v = rl()
	I[r][c] = v

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

for i in range(R+1):
	for j in range(C+1):
		d = dp[i][j]
		for ni, nj in [[i+1, j], [i, j+1]]:
			nd = dp[ni][nj]
			v = I[ni][nj]
			for m in range(4):
				if i == ni:
					nd[m] = max(nd[m], d[m])
					if m < 3:
						nd[m+1] = max(nd[m+1], d[m]+v)
				else:
					nd[0] = max(nd[0], d[m])
					nd[1] = max(nd[1], d[m] + v)
ans = 0
for m in range(4):
	ans = max(ans, dp[R][C][m])
print(ans)


Fixed submission:
import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 1000000007
sys.setrecursionlimit(1000000)
 
R, C, K = rl()
I = [[0]*(C+2) for _ in range(R+2)]
for i in range(K):
	r, c, v = rl()
	I[r][c] = v
 
dp = [[0]*4 for _ in range(C+2)]
dp2 = [[0]*4 for _ in range(C+2)]
 
for i in range(R+1):
	for j in range(C+1):
		for m in range(4):
			ni, nj = i, j+1
			dp[nj][m] = max(dp[nj][m], dp[j][m])
			if m < 3:
				dp[nj][m+1] = max(dp[nj][m+1], dp[j][m]+I[ni][nj])
			ni, nj = i+1, j
			dp2[nj][0] = max(dp2[nj][0], dp[j][m])
			dp2[nj][1] = max(dp2[nj][1], dp[j][m]+I[ni][nj])
	dp = dp2
	dp2 = [[0]*4 for _ in range(C+2)]
ans = 0
for m in range(4):
	ans = max(ans, dp[C][m])
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 1000000007
sys.setrecursionlimit(1000000)

R, C, K = rl()
I = [[0]*(C+2) for _ in range(R+2)]
for i in range(K):
	r, c, v = rl()
	I[r][c] = v

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

for i in range(R+1):
	for j in range(C+1):
		for m in range(4):
			ni, nj = i, j+1
			dp[ni][nj][m] = max(dp[ni][nj][m], dp[i][j][m])
			if m < 3:
				dp[ni][nj][m+1] = max(dp[ni][nj][m+1], dp[i][j][m]+I[ni][nj])
			ni, nj = i+1, j
			dp[ni][nj][0] = max(dp[ni][nj][0], dp[i][j][m])
			dp[ni][nj][1] = max(dp[ni][nj][1], dp[i][j][m]+I[ni][nj])
ans = 0
for m in range(4):
	ans = max(ans, dp[R][C][m])
print(ans)


Fixed submission:
import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 1000000007
sys.setrecursionlimit(1000000)
 
R, C, K = rl()
I = [[0]*(C+2) for _ in range(R+2)]
for i in range(K):
	r, c, v = rl()
	I[r][c] = v
 
dp = [[0]*4 for _ in range(C+2)]
dp2 = [[0]*4 for _ in range(C+2)]
 
for i in range(R+1):
	for j in range(C+1):
		for m in range(4):
			ni, nj = i, j+1
			dp[nj][m] = max(dp[nj][m], dp[j][m])
			if m < 3:
				dp[nj][m+1] = max(dp[nj][m+1], dp[j][m]+I[ni][nj])
			ni, nj = i+1, j
			dp2[nj][0] = max(dp2[nj][0], dp[j][m])
			dp2[nj][1] = max(dp2[nj][1], dp[j][m]+I[ni][nj])
	dp = dp2
	dp2 = [[0]*4 for _ in range(C+2)]
ans = 0
for m in range(4):
	ans = max(ans, dp[C][m])
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 1000000007
sys.setrecursionlimit(1000000)

R, C, K = rl()
I = {}
for i in range(K):
	r, c, v = rl()
	I[(r, c)] = v

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

for i in range(R+1):
	for j in range(C+1):
		for m in range(4):
			ni, nj = i, j+1
			dp[ni][nj][m] = max(dp[ni][nj][m], dp[i][j][m])
			if m < 3 and (ni,nj) in I:
				dp[ni][nj][m+1] = max(dp[ni][nj][m+1], dp[i][j][m]+I[(ni,nj)])

			ni, nj = i+1, j
			dp[ni][nj][0] = max(dp[ni][nj][0], dp[i][j][m])
			if (ni, nj) in I:
				dp[ni][nj][1] = max(dp[ni][nj][1], dp[i][j][m]+I[(ni,nj)])
ans = 0
for m in range(4):
	ans = max(ans, dp[R][C][m])
print(ans)


Fixed submission:
import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 1000000007
sys.setrecursionlimit(1000000)
 
R, C, K = rl()
I = [[0]*(C+2) for _ in range(R+2)]
for i in range(K):
	r, c, v = rl()
	I[r][c] = v
 
dp = [[0]*4 for _ in range(C+2)]
dp2 = [[0]*4 for _ in range(C+2)]
 
for i in range(R+1):
	for j in range(C+1):
		for m in range(4):
			ni, nj = i, j+1
			dp[nj][m] = max(dp[nj][m], dp[j][m])
			if m < 3:
				dp[nj][m+1] = max(dp[nj][m+1], dp[j][m]+I[ni][nj])
			ni, nj = i+1, j
			dp2[nj][0] = max(dp2[nj][0], dp[j][m])
			dp2[nj][1] = max(dp2[nj][1], dp[j][m]+I[ni][nj])
	dp = dp2
	dp2 = [[0]*4 for _ in range(C+2)]
ans = 0
for m in range(4):
	ans = max(ans, dp[C][m])
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 1000000007
sys.setrecursionlimit(1000000)

R, C, K = rl()
I = {}
for i in range(K):
	r, c, v = rl()
	I[(r-1, c-1)] = v

#dist = [[[-float('inf')]*3 for _ in range(C)] for _ in range(R)]
dist = defaultdict(lambda: -float('inf'))
dist[(0, 0, 0, 0)] = 0
heap = []
heappush(heap, (-0, (0, 0, 0, 0)))
ans = 0
while heap:
	d, n = heappop(heap)
	d = -d
	r, c, m, f = n
	#print('rcm', r, c, m, d, f)
	if r == R-1 and c == C-1:
		#print(dist)
		if m < 3 and f == 0:
			if (r, c) in I:
				d += I[(r,c)]
		ans = max(ans, d)
		#break
		continue
	if dist[n] != d:
		continue
	for i, j, k in [[0, 1, m], [1, 0, 0]]:
		ni, nj = r+i, c+j
		if ni >= R or nj >= C: continue
		nn = (ni, nj, k, 0)
		if dist[nn] < d:
			dist[nn] = d
			heappush(heap, (-d, nn))
	if m < 3 and f == 0:
		if (r, c) in I:
			nn = (r, c, m+1, 1)
			nd = d + I[(r,c)]
			if dist[nn] < nd:
				dist[nn] = nd
				heappush(heap, (-nd, nn))
print(ans)


Fixed submission:
import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 1000000007
sys.setrecursionlimit(1000000)
 
R, C, K = rl()
I = [[0]*(C+2) for _ in range(R+2)]
for i in range(K):
	r, c, v = rl()
	I[r][c] = v
 
dp = [[0]*4 for _ in range(C+2)]
dp2 = [[0]*4 for _ in range(C+2)]
 
for i in range(R+1):
	for j in range(C+1):
		for m in range(4):
			ni, nj = i, j+1
			dp[nj][m] = max(dp[nj][m], dp[j][m])
			if m < 3:
				dp[nj][m+1] = max(dp[nj][m+1], dp[j][m]+I[ni][nj])
			ni, nj = i+1, j
			dp2[nj][0] = max(dp2[nj][0], dp[j][m])
			dp2[nj][1] = max(dp2[nj][1], dp[j][m]+I[ni][nj])
	dp = dp2
	dp2 = [[0]*4 for _ in range(C+2)]
ans = 0
for m in range(4):
	ans = max(ans, dp[C][m])
print(ans)