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

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

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

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

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

for h in range(R):
    for w in range(C):
        if h!=0:
            dp[0][h][w] = max(dp[0][h][w], dp[0][h-1][w], dp[1][h-1][w],  dp[2][h-1][w],  dp[3][h-1][w])
            dp[1][h][w] = max(dp[1][h][w], dp[0][h-1][w]+item[h][w], dp[1][h-1][w]+item[h][w], dp[2][h-1][w]+item[h][w], dp[3][h-1][w]+item[h][w])
        if w!=0:
            dp[0][h][w] = max(dp[0][h][w], dp[0][h][w-1])
            dp[1][h][w] = max(dp[1][h][w], dp[1][h][w-1], dp[0][h][w-1]+item[h][w])
            dp[2][h][w] = max(dp[2][h][w], dp[2][h][w-1], dp[1][h][w-1]+item[h][w])
            dp[3][h][w] = max(dp[3][h][w], dp[3][h][w-1], dp[2][h][w-1]+item[h][w])
ans = []
for k in range(4):
    ans.append(dp[k][-1][-1])
print(max(ans))

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

grid = [[0 for c in range(C)] for r in range(R)]

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

dp = [[[-1000 for c in range(C)] for r in range(R)] for k in range(4)]

if grid[0][0] > 0:
    dp[1][0][0] = grid[0][0]
dp[0][0][0] = 0

for r in range(R):
    for c in range(C):
        if c >= 1:
            dp[0][r][c] = max(dp[0][r][c], dp[0][r][c-1])
            dp[1][r][c] = max(dp[1][r][c], dp[1][r][c-1])
            dp[2][r][c] = max(dp[2][r][c], dp[2][r][c-1])
            dp[3][r][c] = max(dp[3][r][c], dp[3][r][c-1])
        if r >= 1:
            dp[0][r][c] = max(dp[0][r][c], dp[0][r-1][c], dp[1][r-1][c], dp[2][r-1][c], dp[3][r-1][c])
        v = grid[r][c]
        if v > 0:
            if c >= 1:
                dp[1][r][c] = max(dp[1][r][c], dp[0][r][c-1] + v)
                dp[2][r][c] = max(dp[2][r][c], dp[1][r][c-1] + v)
                dp[3][r][c] = max(dp[3][r][c], dp[2][r][c-1] + v)
            if r >= 1:
                dp[1][r][c] = max(dp[1][r][c], dp[0][r-1][c]+v, dp[1][r-1][c]+v, dp[2][r-1][c]+v, dp[3][r-1][c]+v)

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

Solution (Python):
import base64

exec(base64.b64decode(b'aW1wb3J0IHN1YnByb2Nlc3MKaW1wb3J0IHN5cwoKY29kZSA9IHIiIiIjaW5jbHVkZSA8YWxnb3JpdGhtPgojaW5jbHVkZSA8Yml0c2V0PgojaW5jbHVkZSA8Y2Fzc2VydD4KI2luY2x1ZGUgPGNjdHlwZT4KI2luY2x1ZGUgPGNocm9ubz4KI2luY2x1ZGUgPGNtYXRoPgojaW5jbHVkZSA8Y29tcGxleD4KI2luY2x1ZGUgPGNzdHJpbmc+CiNpbmNsdWRlIDxkZXF1ZT4KI2luY2x1ZGUgPGlvbWFuaXA+CiNpbmNsdWRlIDxpb3N0cmVhbT4KI2luY2x1ZGUgPG1hcD4KI2luY2x1ZGUgPG51bWVyaWM+CiNpbmNsdWRlIDxxdWV1ZT4KI2luY2x1ZGUgPHJhbmRvbT4KI2luY2x1ZGUgPHNldD4KI2luY2x1ZGUgPHN0YWNrPgojaW5jbHVkZSA8c3RyaW5nPgojaW5jbHVkZSA8dHVwbGU+CiNpbmNsdWRlIDx1dGlsaXR5PgojaW5jbHVkZSA8dmVjdG9yPgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCnVzaW5nIGludDY0ID0gbG9uZyBsb25nOwoKI2RlZmluZSBhbGwoXykgYmVnaW4oXyksIGVuZChfKQojZGVmaW5lIHJhbGwoXykgcmJlZ2luKF8pLCByZW5kKF8pCgppbnQ2NCBkcFszMDAwXVszMDAwXVs0XTsKCmludCBtYWluKCkgewogIGlvc19iYXNlOjpzeW5jX3dpdGhfc3RkaW8oZmFsc2UpOwogIGNpbi50aWUobnVsbHB0cik7CgogIGludCByLCBjLCBrOyBjaW4gPj4gciA+PiBjID4+IGs7CiAgaW50IHZhbFtyXVtjXTsKICBmaWxsKHZhbFswXSwgdmFsW3JdLCAwKTsKICBmb3IgKGludCBpID0gMDsgaSA8IGs7ICsraSkgewogICAgaW50IHgsIHksIHo7IGNpbiA+PiB4ID4+IHkgPj4gejsKICAgIC0teDsgLS15OwogICAgdmFsW3hdW3ldID0gejsKICB9CgogIGlmICh2YWxbMF1bMF0gIT0gMCkgZHBbMF1bMF1bMV0gPSB2YWxbMF1bMF07CgogIGZvciAoaW50IGkgPSAwOyBpIDwgcjsgKytpKSB7CiAgICBmb3IgKGludCBqID0gMDsgaiA8IGM7ICsraikgewogICAgICBpZiAoaSA9PSAwICYmIGogPT0gMCkgY29udGludWU7CgogICAgICBpZiAodmFsW2ldW2pdICE9IDApIHsKICAgICAgICBpZiAoaSA+IDApIHsKICAgICAgICAgIGZvciAoaW50IGwgPSAwOyBsIDwgNDsgKytsKSBkcFtpXVtqXVswXSA9IG1heChkcFtpXVtqXVswXSwgZHBbaSAtIDFdW2pdW2xdKTsKICAgICAgICAgIGZvciAoaW50IGwgPSAwOyBsIDwgNDsgKytsKSBkcFtpXVtqXVsxXSA9IG1heChkcFtpXVtqXVsxXSwgZHBbaSAtIDFdW2pdW2xdICsgdmFsW2ldW2pdKTsKICAgICAgICB9CiAgICAgICAgaWYgKGogPiAwKSB7CiAgICAgICAgICBkcFtpXVtqXVswXSA9IG1heChkcFtpXVtqXVswXSwgZHBbaV1baiAtIDFdWzBdKTsKICAgICAgICAgIGZvciAoaW50IGwgPSAxOyBsIDwgNDsgKytsKSB7CiAgICAgICAgICAgIGRwW2ldW2pdW2xdID0gbWF4KHtkcFtpXVtqXVtsXSwgZHBbaV1baiAtIDFdW2xdLCBkcFtpXVtqIC0gMV1bbCAtIDFdICsgdmFsW2ldW2pdfSk7CiAgICAgICAgICB9CiAgICAgICAgfQogICAgICB9IGVsc2UgewogICAgICAgIGlmIChpID4gMCkgewogICAgICAgICAgZm9yIChpbnQgbCA9IDA7IGwgPCA0OyArK2wpIGRwW2ldW2pdWzBdID0gbWF4KGRwW2ldW2pdWzBdLCBkcFtpIC0gMV1bal1bbF0pOwogICAgICAgIH0KICAgICAgICBpZiAoaiA+IDApIHsKICAgICAgICAgIGZvciAoaW50IGwgPSAwOyBsIDwgNDsgKytsKSBkcFtpXVtqXVtsXSA9IG1heChkcFtpXVtqXVtsXSwgZHBbaV1baiAtIDFdW2xdKTsKICAgICAgICB9CiAgICAgIH0KICAgIH0KICB9CgogIGludDY0IGFucyA9IDA7CiAgZm9yIChpbnQgaSA9IDA7IGkgPCA0OyArK2kpIGFucyA9IG1heChhbnMsIGRwW3IgLSAxXVtjIC0gMV1baV0pOwogIGNvdXQgPDwgYW5zIDw8IGVuZGw7CgogIHJldHVybiAwOwp9CiIiIgoKd2l0aCBvcGVuKCdzb2wuY3BwJywgJ3cnKSBhcyBmOgogICAgZi53cml0ZShjb2RlKQoKc3VicHJvY2Vzcy5Qb3BlbihbJ2crKycsICctc3RkPWMrKzE3JywgJy1PMicsICdzb2wuY3BwJ10pLmNvbW11bmljYXRlKCkKc3VicHJvY2Vzcy5Qb3BlbihbJy4vYS5vdXQnXSwgc3RkaW49c3lzLnN0ZGluLCBzdGRvdXQ9c3lzLnN0ZG91dCkuY29tbXVuaWNhdGUoKQ=='))

Solution (Python):
import base64

exec(base64.b64decode(b'aW1wb3J0IHN1YnByb2Nlc3MKaW1wb3J0IHN5cwoKY29kZSA9IHIiIiIjcHJhZ21hIEdDQyBvcHRpbWl6ZSgidW5yb2xsLWxvb3BzIikKCiNpbmNsdWRlIDxhbGdvcml0aG0+CiNpbmNsdWRlIDxiaXRzZXQ+CiNpbmNsdWRlIDxjYXNzZXJ0PgojaW5jbHVkZSA8Y2N0eXBlPgojaW5jbHVkZSA8Y2hyb25vPgojaW5jbHVkZSA8Y21hdGg+CiNpbmNsdWRlIDxjb21wbGV4PgojaW5jbHVkZSA8Y3N0cmluZz4KI2luY2x1ZGUgPGRlcXVlPgojaW5jbHVkZSA8aW9tYW5pcD4KI2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8bWFwPgojaW5jbHVkZSA8bnVtZXJpYz4KI2luY2x1ZGUgPHF1ZXVlPgojaW5jbHVkZSA8cmFuZG9tPgojaW5jbHVkZSA8c2V0PgojaW5jbHVkZSA8c3RhY2s+CiNpbmNsdWRlIDxzdHJpbmc+CiNpbmNsdWRlIDx0dXBsZT4KI2luY2x1ZGUgPHV0aWxpdHk+CiNpbmNsdWRlIDx2ZWN0b3I+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKdXNpbmcgaW50NjQgPSBsb25nIGxvbmc7CgojZGVmaW5lIGFsbChfKSBiZWdpbihfKSwgZW5kKF8pCiNkZWZpbmUgcmFsbChfKSByYmVnaW4oXyksIHJlbmQoXykKCmludDY0IGRwWzMwMDBdWzMwMDBdWzRdOwoKbmFtZXNwYWNlIEZhc3RJTyB7CmNsYXNzIFNjYW5uZXIgewogIHN0YXRpYyBjb25zdGV4cHIgaW50IGJ1Zl9zaXplID0gKDEgPDwgMTgpOwogIHN0YXRpYyBjb25zdGV4cHIgaW50IGludGVnZXJfc2l6ZSA9IDIwOwogIHN0YXRpYyBjb25zdGV4cHIgaW50IHN0cmluZ19zaXplID0gMTAwMDsgLy8gZGVmYXVsdAogIGNoYXIgYnVmW2J1Zl9zaXplXSA9IHt9OwogIGNoYXIgKmN1ciA9IGJ1ZiwgKmVkID0gYnVmOwoKIHB1YmxpYzoKICBTY2FubmVyKCkge30KCiAgdGVtcGxhdGUgPGNsYXNzIFQ+CiAgaW5saW5lIFNjYW5uZXImIG9wZXJhdG9yPj4oVCYgdmFsKSB7CiAgICByZWFkKHZhbCk7CiAgICByZXR1cm4gKnRoaXM7CiAgfQoKIHByaXZhdGU6CiAgaW5saW5lIHZvaWQgcmVsb2FkKCkgewogICAgc2l6ZV90IGxlbiA9IGVkIC0gY3VyOwogICAgbWVtbW92ZShidWYsIGN1ciwgbGVuKTsKICAgIGNoYXIqIHRtcCA9IGJ1ZiArIGxlbjsKICAgIGVkID0gdG1wICsgZnJlYWQodG1wLCAxLCBidWZfc2l6ZSAtIGxlbiwgc3RkaW4pOwogICAgKmVkID0gMDsKICAgIGN1ciA9IGJ1ZjsKICB9CgogIGlubGluZSB2b2lkIHNraXBfc3BhY2UoKSB7CiAgICB3aGlsZSAodHJ1ZSkgewogICAgICBpZiAoY3VyID09IGVkKSByZWxvYWQoKTsKICAgICAgd2hpbGUgKCpjdXIgPT0gJyAnIHx8ICpjdXIgPT0gJ1xuJykgKytjdXI7CiAgICAgIGlmIChfX2J1aWx0aW5fZXhwZWN0KGN1ciAhPSBlZCwgMSkpIHJldHVybjsKICAgIH0KICB9CgogIHRlbXBsYXRlIDxjbGFzcyBULCBzdGQ6OmVuYWJsZV9pZl90PHN0ZDo6aXNfc2FtZTxULCBpbnQ+Ojp2YWx1ZSwgaW50PiA9IDA+CiAgaW5saW5lIHZvaWQgcmVhZChUJiBudW0pIHsKICAgIHNraXBfc3BhY2UoKTsKICAgIGlmIChjdXIgKyBpbnRlZ2VyX3NpemUgPj0gZWQpIHJlbG9hZCgpOwogICAgYm9vbCBuZWcgPSBmYWxzZTsKICAgIG51bSA9IDA7CiAgICBpZiAoKmN1ciA9PSAnLScpIG5lZyA9IHRydWUsICsrY3VyOwogICAgd2hpbGUgKCpjdXIgPj0gJzAnKSBudW0gPSBudW0gKiAxMCArICgqY3VyIF4gNDgpLCArK2N1cjsKICAgIGlmIChuZWcpIG51bSA9IC1udW07CiAgfQoKICB0ZW1wbGF0ZSA8Y2xhc3MgVCwgc3RkOjplbmFibGVfaWZfdDxzdGQ6OmlzX3NhbWU8VCwgaW50NjQ+Ojp2YWx1ZSwgaW50PiA9IDA+CiAgaW5saW5lIHZvaWQgcmVhZChUJiBudW0pIHsKICAgIHNraXBfc3BhY2UoKTsKICAgIGlmIChjdXIgKyBpbnRlZ2VyX3NpemUgPj0gZWQpIHJlbG9hZCgpOwogICAgYm9vbCBuZWcgPSBmYWxzZTsKICAgIG51bSA9IDA7CiAgICBpZiAoKmN1ciA9PSAnLScpIG5lZyA9IHRydWUsICsrY3VyOwogICAgd2hpbGUgKCpjdXIgPj0gJzAnKSBudW0gPSBudW0gKiAxMCArICgqY3VyIF4gNDgpLCArK2N1cjsKICAgIGlmIChuZWcpIG51bSA9IC1udW07CiAgfQoKICB0ZW1wbGF0ZSA8Y2xhc3MgVCwKICAgICAgICAgICAgc3RkOjplbmFibGVfaWZfdDxzdGQ6OmlzX3NhbWU8VCwgc3RkOjpzdHJpbmc+Ojp2YWx1ZSwgaW50PiA9IDA+CiAgaW5saW5lIHZvaWQgcmVhZChUJiBzdHIpIHsKICAgIHNraXBfc3BhY2UoKTsKICAgIGlmIChjdXIgKyBzdHIuc2l6ZSgpID49IGVkKSByZWxvYWQoKTsKICAgIGF1dG8gaXQgPSBjdXI7CiAgICB3aGlsZSAoISgqY3VyID09ICcgJyB8fCAqY3VyID09ICdcbicpKSArK2N1cjsKICAgIHN0ciA9IHN0ZDo6c3RyaW5nKGl0LCBjdXIpOwogIH0KCiAgdGVtcGxhdGUgPGNsYXNzIFQsIHN0ZDo6ZW5hYmxlX2lmX3Q8c3RkOjppc19zYW1lPFQsIGNoYXI+Ojp2YWx1ZSwgaW50PiA9IDA+CiAgaW5saW5lIHZvaWQgcmVhZChUJiBjKSB7CiAgICBza2lwX3NwYWNlKCk7CiAgICBpZiAoY3VyICsgMSA+PSBlZCkgcmVsb2FkKCk7CiAgICBjID0gKmN1ciwgKytjdXI7CiAgfQoKICB0ZW1wbGF0ZSA8Y2xhc3MgVCwgc3RkOjplbmFibGVfaWZfdDxzdGQ6OmlzX3NhbWU8VCwgZG91YmxlPjo6dmFsdWUsIGludD4gPSAwPgogIGlubGluZSB2b2lkIHJlYWQoVCYgbnVtKSB7CiAgICBza2lwX3NwYWNlKCk7CiAgICBpZiAoY3VyICsgaW50ZWdlcl9zaXplID49IGVkKSByZWxvYWQoKTsKICAgIGJvb2wgbmVnID0gZmFsc2U7CiAgICBudW0gPSAwOwogICAgaWYgKCpjdXIgPT0gJy0nKSBuZWcgPSB0cnVlLCArK2N1cjsKICAgIHdoaWxlICgqY3VyID49ICcwJyAmJiAqY3VyIDw9ICc5JykgbnVtID0gbnVtICogMTAgKyAoKmN1ciBeIDQ4KSwgKytjdXI7CiAgICBpZiAoKmN1ciAhPSAnLicpIHJldHVybjsKICAgICsrY3VyOwogICAgVCBiYXNlID0gMC4xOwogICAgd2hpbGUgKCpjdXIgPj0gJzAnICYmICpjdXIgPD0gJzknKSB7CiAgICAgIG51bSArPSBiYXNlICogKCpjdXIgXiA0OCk7CiAgICAgICsrY3VyOwogICAgICBiYXNlICo9IDAuMTsKICAgIH0KICAgIGlmIChuZWcpIG51bSA9IC1udW07CiAgfQoKICB0ZW1wbGF0ZSA8Y2xhc3MgVCwKICAgICAgICAgICAgc3RkOjplbmFibGVfaWZfdDxzdGQ6OmlzX3NhbWU8VCwgbG9uZyBkb3VibGU+Ojp2YWx1ZSwgaW50PiA9IDA+CiAgaW5saW5lIHZvaWQgcmVhZChUJiBudW0pIHsKICAgIHNraXBfc3BhY2UoKTsKICAgIGlmIChjdXIgKyBpbnRlZ2VyX3NpemUgPj0gZWQpIHJlbG9hZCgpOwogICAgYm9vbCBuZWcgPSBmYWxzZTsKICAgIG51bSA9IDA7CiAgICBpZiAoKmN1ciA9PSAnLScpIG5lZyA9IHRydWUsICsrY3VyOwogICAgd2hpbGUgKCpjdXIgPj0gJzAnICYmICpjdXIgPD0gJzknKSBudW0gPSBudW0gKiAxMCArICgqY3VyIF4gNDgpLCArK2N1cjsKICAgIGlmICgqY3VyICE9ICcuJykgcmV0dXJuOwogICAgKytjdXI7CiAgICBUIGJhc2UgPSAwLjE7CiAgICB3aGlsZSAoKmN1ciA+PSAnMCcgJiYgKmN1ciA8PSAnOScpIHsKICAgICAgbnVtICs9IGJhc2UgKiAoKmN1ciBeIDQ4KTsKICAgICAgKytjdXI7CiAgICAgIGJhc2UgKj0gMC4xOwogICAgfQogICAgaWYgKG5lZykgbnVtID0gLW51bTsKICB9CgogIHRlbXBsYXRlIDxjbGFzcyBUPgogIGlubGluZSB2b2lkIHJlYWQoc3RkOjp2ZWN0b3I8VD4mIHZlYykgewogICAgZm9yIChUJiBlIDogdmVjKSByZWFkKGUpOwogIH0KCiAgdGVtcGxhdGUgPGNsYXNzIFQsIGNsYXNzIFU+CiAgaW5saW5lIHZvaWQgcmVhZChzdGQ6OnBhaXI8VCwgVT4mIHApIHsKICAgIHJlYWQocC5maXJzdCwgcC5zZWNvbmQpOwogIH0KCiAgdGVtcGxhdGUgPGNsYXNzIFR1cGxlLCBzdGQ6OnNpemVfdC4uLiBJcz4KICBpbmxpbmUgdm9pZCB0dXBsZV9zY2FuKFR1cGxlJiB0cCwgc3RkOjppbmRleF9zZXF1ZW5jZTxJcy4uLj4pIHsKICAgIChyZWFkKHN0ZDo6Z2V0PElzPih0cCkpLCAuLi4pOwogIH0KCiAgdGVtcGxhdGUgPGNsYXNzLi4uIEFyZ3M+CiAgaW5saW5lIHZvaWQgcmVhZChzdGQ6OnR1cGxlPEFyZ3MuLi4+JiB0cCkgewogICAgdHVwbGVfc2Nhbih0cCwgc3RkOjppbmRleF9zZXF1ZW5jZV9mb3I8QXJncy4uLj57fSk7CiAgfQoKICBpbmxpbmUgdm9pZCByZWFkKCkge30KCiAgdGVtcGxhdGUgPGNsYXNzIEhlYWQsIGNsYXNzLi4uIFRhaWw+CiAgaW5saW5lIHZvaWQgcmVhZChIZWFkJiYgaGVhZCwgVGFpbCYmLi4uIHRhaWwpIHsKICAgIHJlYWQoaGVhZCk7CiAgICByZWFkKHN0ZDo6Zm9yd2FyZDxUYWlsPih0YWlsKS4uLik7CiAgfQp9OwoKY2xhc3MgUHJpbnRlciB7CiAgc3RhdGljIGNvbnN0ZXhwciBpbnQgYnVmX3NpemUgPSAoMSA8PCAxOCk7CiAgc3RhdGljIGNvbnN0ZXhwciBpbnQgaW50ZWdlcl9zaXplID0gMjA7CiAgc3RhdGljIGNvbnN0ZXhwciBpbnQgc3RyaW5nX3NpemUgPSAoMSA8PCA2KTsKICBzdGF0aWMgY29uc3RleHByIGludCBtYXJnaW4gPSAxOwogIHN0YXRpYyBjb25zdGV4cHIgaW50IG4gPSAxMDAwMDsKICBjaGFyIGJ1ZltidWZfc2l6ZSArIG1hcmdpbl0gPSB7fTsKICBjaGFyIHRhYmxlW24gKiA0XSA9IHt9OwogIGNoYXIqIGN1ciA9IGJ1ZjsKCiBwdWJsaWM6CiAgY29uc3RleHByIFByaW50ZXIoKSB7IGJ1aWxkKCk7IH0KCiAgflByaW50ZXIoKSB7IGZsdXNoKCk7IH0KCiAgdGVtcGxhdGUgPGNsYXNzIFQ+CiAgaW5saW5lIFByaW50ZXImIG9wZXJhdG9yPDwoVCB2YWwpIHsKICAgIHdyaXRlKHZhbCk7CiAgICByZXR1cm4gKnRoaXM7CiAgfQoKICB0ZW1wbGF0ZTxjbGFzcyBUPgogIGlubGluZSB2b2lkIHByaW50bG4oVCB2YWwpIHsKICAgIHdyaXRlKHZhbCk7CiAgICB3cml0ZSgnXG4nKTsKICB9CgogcHJpdmF0ZToKICBjb25zdGV4cHIgdm9pZCBidWlsZCgpIHsKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgMTAwMDA7ICsraSkgewogICAgICBpbnQgdG1wID0gaTsKICAgICAgZm9yIChpbnQgaiA9IDM7IGogPj0gMDsgLS1qKSB7CiAgICAgICAgdGFibGVbaSAqIDQgKyBqXSA9IHRtcCAlIDEwICsgJzAnOwogICAgICAgIHRtcCAvPSAxMDsKICAgICAgfQogICAgfQogIH0KCiAgaW5saW5lIHZvaWQgZmx1c2goKSB7CiAgICBmd3JpdGUoYnVmLCAxLCBjdXIgLSBidWYsIHN0ZG91dCk7CiAgICBjdXIgPSBidWY7CiAgfQoKICB0ZW1wbGF0ZSA8Y2xhc3MgVCwgc3RkOjplbmFibGVfaWZfdDxzdGQ6OmlzX3NhbWU8VCwgaW50Pjo6dmFsdWUsIGludD4gPSAwPgogIGlubGluZSBpbnQgZ2V0X2RpZ2l0KFQgbikgewogICAgaWYgKG4gPj0gKGludCkxZTUpIHsKICAgICAgaWYgKG4gPj0gKGludCkxZTgpIHJldHVybiA5OwogICAgICBpZiAobiA+PSAoaW50KTFlNykgcmV0dXJuIDg7CiAgICAgIGlmIChuID49IChpbnQpMWU2KSByZXR1cm4gNzsKICAgICAgcmV0dXJuIDY7CiAgICB9IGVsc2UgewogICAgICBpZiAobiA+PSAoaW50KTFlNCkgcmV0dXJuIDU7CiAgICAgIGlmIChuID49IChpbnQpMWUzKSByZXR1cm4gNDsKICAgICAgaWYgKG4gPj0gKGludCkxZTIpIHJldHVybiAzOwogICAgICBpZiAobiA+PSAoaW50KTFlMSkgcmV0dXJuIDI7CiAgICAgIHJldHVybiAxOwogICAgfQogIH0KCiAgdGVtcGxhdGUgPGNsYXNzIFQsIHN0ZDo6ZW5hYmxlX2lmX3Q8c3RkOjppc19zYW1lPFQsIGludDY0Pjo6dmFsdWUsIGludD4gPSAwPgogIGlubGluZSBpbnQgZ2V0X2RpZ2l0KFQgbikgewogICAgaWYgKG4gPj0gKGludDY0KTFlMTApIHsKICAgICAgaWYgKG4gPj0gKGludDY0KTFlMTQpIHsKICAgICAgICBpZiAobiA+PSAoaW50NjQpMWUxOCkgcmV0dXJuIDE5OwogICAgICAgIGlmIChuID49IChpbnQ2NCkxZTE3KSByZXR1cm4gMTg7CiAgICAgICAgaWYgKG4gPj0gKGludDY0KTFlMTYpIHJldHVybiAxNzsKICAgICAgICBpZiAobiA+PSAoaW50NjQpMWUxNSkgcmV0dXJuIDE2OwogICAgICAgIHJldHVybiAxNTsKICAgICAgfSBlbHNlIHsKICAgICAgICBpZiAobiA+PSAoaW50NjQpMWUxNCkgcmV0dXJuIDE1OwogICAgICAgIGlmIChuID49IChpbnQ2NCkxZTEzKSByZXR1cm4gMTQ7CiAgICAgICAgaWYgKG4gPj0gKGludDY0KTFlMTIpIHJldHVybiAxMzsKICAgICAgICBpZiAobiA+PSAoaW50NjQpMWUxMSkgcmV0dXJuIDEyOwogICAgICAgIHJldHVybiAxMTsKICAgICAgfQogICAgfSBlbHNlIHsKICAgICAgaWYgKG4gPj0gKGludDY0KTFlNSkgewogICAgICAgIGlmIChuID49IChpbnQ2NCkxZTkpIHJldHVybiAxMDsKICAgICAgICBpZiAobiA+PSAoaW50NjQpMWU4KSByZXR1cm4gOTsKICAgICAgICBpZiAobiA+PSAoaW50NjQpMWU3KSByZXR1cm4gODsKICAgICAgICBpZiAobiA+PSAoaW50NjQpMWU2KSByZXR1cm4gNzsKICAgICAgICByZXR1cm4gNjsKICAgICAgfSBlbHNlIHsKICAgICAgICBpZiAobiA+PSAoaW50NjQpMWU0KSByZXR1cm4gNTsKICAgICAgICBpZiAobiA+PSAoaW50NjQpMWUzKSByZXR1cm4gNDsKICAgICAgICBpZiAobiA+PSAoaW50NjQpMWUyKSByZXR1cm4gMzsKICAgICAgICBpZiAobiA+PSAoaW50NjQpMWUxKSByZXR1cm4gMjsKICAgICAgICByZXR1cm4gMTsKICAgICAgfQogICAgfQogIH0KCiAgdGVtcGxhdGUgPGNsYXNzIFQsIHN0ZDo6ZW5hYmxlX2lmX3Q8c3RkOjppc19zYW1lPFQsIGludD46OnZhbHVlLCBpbnQ+ID0gMD4KICBpbmxpbmUgdm9pZCB3cml0ZShUIG51bSkgewogICAgaWYgKF9fYnVpbHRpbl9leHBlY3QoY3VyICsgaW50ZWdlcl9zaXplID49IGJ1ZiArIGJ1Zl9zaXplLCAwKSkgZmx1c2goKTsKICAgIGlmIChudW0gPT0gMCkgewogICAgICB3cml0ZSgnMCcpOwogICAgICByZXR1cm47CiAgICB9CiAgICBpZiAobnVtIDwgMCkgewogICAgICB3cml0ZSgnLScpOwogICAgICBudW0gPSAtbnVtOwogICAgfQogICAgaW50IGxlbiA9IGdldF9kaWdpdChudW0pOwogICAgaW50IGRpZ2l0cyA9IGxlbjsKICAgIHdoaWxlIChudW0gPj0gMTAwMDApIHsKICAgICAgbWVtY3B5KGN1ciArIGxlbiAtIDQsIHRhYmxlICsgKG51bSAlIDEwMDAwKSAqIDQsIDQpOwogICAgICBudW0gLz0gMTAwMDA7CiAgICAgIGxlbiAtPSA0OwogICAgfQogICAgbWVtY3B5KGN1ciwgdGFibGUgKyBudW0gKiA0ICsgKDQgLSBsZW4pLCBsZW4pOwogICAgY3VyICs9IGRpZ2l0czsKICB9CgogIHRlbXBsYXRlIDxjbGFzcyBULCBzdGQ6OmVuYWJsZV9pZl90PHN0ZDo6aXNfc2FtZTxULCBpbnQ2ND46OnZhbHVlLCBpbnQ+ID0gMD4KICBpbmxpbmUgdm9pZCB3cml0ZShUIG51bSkgewogICAgaWYgKF9fYnVpbHRpbl9leHBlY3QoY3VyICsgaW50ZWdlcl9zaXplID49IGJ1ZiArIGJ1Zl9zaXplLCAwKSkgZmx1c2goKTsKICAgIGlmIChudW0gPT0gMCkgewogICAgICB3cml0ZSgnMCcpOwogICAgICByZXR1cm47CiAgICB9CiAgICBpZiAobnVtIDwgMCkgewogICAgICB3cml0ZSgnLScpOwogICAgICBudW0gPSAtbnVtOwogICAgfQogICAgaW50IGxlbiA9IGdldF9kaWdpdChudW0pOwogICAgaW50IGRpZ2l0cyA9IGxlbjsKICAgIHdoaWxlIChudW0gPj0gMTAwMDApIHsKICAgICAgbWVtY3B5KGN1ciArIGxlbiAtIDQsIHRhYmxlICsgKG51bSAlIDEwMDAwKSAqIDQsIDQpOwogICAgICBudW0gLz0gMTAwMDA7CiAgICAgIGxlbiAtPSA0OwogICAgfQogICAgbWVtY3B5KGN1ciwgdGFibGUgKyBudW0gKiA0ICsgKDQgLSBsZW4pLCBsZW4pOwogICAgY3VyICs9IGRpZ2l0czsKICB9CgogIHRlbXBsYXRlIDxjbGFzcyBULCBzdGQ6OmVuYWJsZV9pZl90PHN0ZDo6aXNfc2FtZTxULCBjaGFyPjo6dmFsdWUsIGludD4gPSAwPgogIGlubGluZSB2b2lkIHdyaXRlKFQgYykgewogICAgaWYgKF9fYnVpbHRpbl9leHBlY3QoY3VyICsgMSA+PSBidWYgKyBidWZfc2l6ZSwgMCkpIGZsdXNoKCk7CiAgICAqY3VyID0gYzsKICAgICsrY3VyOwogIH0KCiAgdGVtcGxhdGUgPGNsYXNzIFQsCiAgICAgICAgICAgIHN0ZDo6ZW5hYmxlX2lmX3Q8c3RkOjppc19zYW1lPFQsIHN0ZDo6c3RyaW5nPjo6dmFsdWUsIGludD4gPSAwPgogIGlubGluZSB2b2lkIHdyaXRlKFQgc3RyKSB7CiAgICBpZiAoX19idWlsdGluX2V4cGVjdChjdXIgKyBzdHIuc2l6ZSgpID49IGJ1ZiArIGJ1Zl9zaXplLCAwKSkgZmx1c2goKTsKICAgIGZvciAoY2hhciBjIDogc3RyKSB3cml0ZShjKTsKICB9CgogIHRlbXBsYXRlIDxjbGFzcyBULAogICAgICAgICAgICBzdGQ6OmVuYWJsZV9pZl90PHN0ZDo6aXNfc2FtZTxULCBjb25zdCBjaGFyKj46OnZhbHVlLCBpbnQ+ID0gMD4KICBpbmxpbmUgdm9pZCB3cml0ZShUIHN0cikgewogICAgaWYgKF9fYnVpbHRpbl9leHBlY3QoY3VyICsgc3RyaW5nX3NpemUgPj0gYnVmICsgYnVmX3NpemUsIDApKSBmbHVzaCgpOwogICAgZm9yIChpbnQgaSA9IDA7IHN0cltpXTsgKytpKSB3cml0ZShzdHJbaV0pOwogIH0KfTsKfSAgLy8gbmFtZXNwYWNlIEZhc3RJTwoKRmFzdElPOjpTY2FubmVyIGZpbjsKRmFzdElPOjpQcmludGVyIGZvdXQ7CgoKaW50IG1haW4oKSB7CiAgaW50IHIsIGMsIGs7IGZpbiA+PiByID4+IGMgPj4gazsKICBpbnQgdmFsW3JdW2NdOwogIGZpbGwodmFsWzBdLCB2YWxbcl0sIDApOwogIGZvciAoaW50IGkgPSAwOyBpIDwgazsgKytpKSB7CiAgICBpbnQgeCwgeSwgejsgZmluID4+IHggPj4geSA+PiB6OwogICAgLS14OyAtLXk7CiAgICB2YWxbeF1beV0gPSB6OwogIH0KCiAgaWYgKHZhbFswXVswXSAhPSAwKSBkcFswXVswXVsxXSA9IHZhbFswXVswXTsKCiAgZm9yIChpbnQgaSA9IDA7IGkgPCByOyArK2kpIHsKICAgIGZvciAoaW50IGogPSAwOyBqIDwgYzsgKytqKSB7CiAgICAgIGlmIChpID09IDAgJiYgaiA9PSAwKSBjb250aW51ZTsKCiAgICAgIGlmICh2YWxbaV1bal0gIT0gMCkgewogICAgICAgIGlmIChpID4gMCkgewogICAgICAgICAgZm9yIChpbnQgbCA9IDA7IGwgPCA0OyArK2wpIGRwW2ldW2pdWzBdID0gbWF4KGRwW2ldW2pdWzBdLCBkcFtpIC0gMV1bal1bbF0pOwogICAgICAgICAgZm9yIChpbnQgbCA9IDA7IGwgPCA0OyArK2wpIGRwW2ldW2pdWzFdID0gbWF4KGRwW2ldW2pdWzFdLCBkcFtpIC0gMV1bal1bbF0gKyB2YWxbaV1bal0pOwogICAgICAgIH0KICAgICAgICBpZiAoaiA+IDApIHsKICAgICAgICAgIGRwW2ldW2pdWzBdID0gbWF4KGRwW2ldW2pdWzBdLCBkcFtpXVtqIC0gMV1bMF0pOwogICAgICAgICAgZm9yIChpbnQgbCA9IDE7IGwgPCA0OyArK2wpIHsKICAgICAgICAgICAgZHBbaV1bal1bbF0gPSBtYXgoe2RwW2ldW2pdW2xdLCBkcFtpXVtqIC0gMV1bbF0sIGRwW2ldW2ogLSAxXVtsIC0gMV0gKyB2YWxbaV1bal19KTsKICAgICAgICAgIH0KICAgICAgICB9CiAgICAgIH0gZWxzZSB7CiAgICAgICAgaWYgKGkgPiAwKSB7CiAgICAgICAgICBmb3IgKGludCBsID0gMDsgbCA8IDQ7ICsrbCkgZHBbaV1bal1bMF0gPSBtYXgoZHBbaV1bal1bMF0sIGRwW2kgLSAxXVtqXVtsXSk7CiAgICAgICAgfQogICAgICAgIGlmIChqID4gMCkgewogICAgICAgICAgZm9yIChpbnQgbCA9IDA7IGwgPCA0OyArK2wpIGRwW2ldW2pdW2xdID0gbWF4KGRwW2ldW2pdW2xdLCBkcFtpXVtqIC0gMV1bbF0pOwogICAgICAgIH0KICAgICAgfQogICAgfQogIH0KCiAgaW50NjQgYW5zID0gMDsKICBmb3IgKGludCBpID0gMDsgaSA8IDQ7ICsraSkgYW5zID0gbWF4KGFucywgZHBbciAtIDFdW2MgLSAxXVtpXSk7CiAgZm91dC5wcmludGxuKGFucyk7CgogIHJldHVybiAwOwp9CiIiIgoKd2l0aCBvcGVuKCdzb2wuY3BwJywgJ3cnKSBhcyBmOgogICAgZi53cml0ZShjb2RlKQoKc3VicHJvY2Vzcy5Qb3BlbihbJ2crKycsICctc3RkPWMrKzE3JywgJy1PMicsICdzb2wuY3BwJ10pLmNvbW11bmljYXRlKCkKc3VicHJvY2Vzcy5Qb3BlbihbJy4vYS5vdXQnXSwgc3RkaW49c3lzLnN0ZGluLCBzdGRvdXQ9c3lzLnN0ZG91dCkuY29tbXVuaWNhdGUoKQ=='))

Solution (Python):

R,C,K = map(int,input().split())
A =     [[0  for j in range(C)] for i in range(R)]
varr = [[[0  for j in range(C)] for i in range(R)] for k in range(4)]

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

for i in range(R):  
    for j in range(C):
        for k in range(2,-1,-1):
            if varr[k][i][j] >= 0:
                if  varr[k+1][i][j] < varr[k][i][j] + A[i][j]:
                    varr[k+1][i][j] = varr[k][i][j] + A[i][j]
        for kk in range(0,4):
            if varr[kk][i][j] >= 0:
                if i +1 < R :
                    if  varr[0][i + 1][j] < varr[kk][i][j]:
                        varr[0][i + 1][j] = varr[kk][i][j] 
                if j +1 < C :
                    if  varr[kk][i][j + 1] < varr[kk][i][j]:
                        varr[kk][i][j + 1] = varr[kk][i][j] 
ans = 0
for k in range (4):
    if ans < varr[k][R-1][C-1]:
        ans = varr[k][R-1][C-1]

print(ans)

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

@njit((i8, i8, i8, i8[:,:]), cache=True)
def solve(R,C,K,item):
  dp = np.zeros((C+1,4), dtype=np.int64)
  for i in range(1,R+1):
    new_dp = np.zeros((C+1,4), dtype=np.int64)
    
    for k in range(4):
      new_dp[:,0] = np.maximum(new_dp[:,0], dp[:,k])
    dp = new_dp
    for j in range(1,C+1):
      
      for k in range(4):
        new_dp[j][k] = np.maximum(new_dp[j,k],new_dp[j-1,k])
      
      for k in range(2,-1,-1):
        dp[j,k+1] = np.maximum(dp[j,k+1],dp[j,k]+item[i-1][j-1])
  ans = dp[-1].max()
  return ans

R, C, K = map(int, input().split())
item = np.zeros((R,C), dtype=np.int64)
for i in range(K):
  r,c,v = map(int, input().split())
  item[r-1,c-1] = v
print(solve(R,C,K,item))

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

@njit((i8, i8, i8, i8[:,:]), cache=True)
def solve(R,C,K,item):
  dp = np.zeros((C+1,4), dtype=np.int64)
  for i in range(1,R+1):
    new_dp = np.zeros((C+1,4), dtype=np.int64)
    
    for k in range(4):
      new_dp[:,0] = np.maximum(new_dp[:,0], dp[:,k])
    dp = new_dp
    for j in range(1,C+1):
      
      for k in range(4):
        new_dp[j][k] = np.maximum(new_dp[j][k],new_dp[j-1][k])
      
      for k in range(2,-1,-1):
        dp[j,k+1] = np.maximum(dp[j,k+1],dp[j,k]+item[i-1][j-1])
  ans = dp[-1].max()
  return ans

R, C, K = map(int, input().split())
item = np.zeros((R,C), dtype=np.int64)
for i in range(K):
  r,c,v = map(int, input().split())
  item[r-1,c-1] = v
print(solve(R,C,K,item))

Solution (Python):
import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

@njit((i8, i8, i8, i8[:]), cache=True)
def solve(R,C,K,XYV):
  item = np.zeros((R + 1, C + 1), dtype=np.int64)
  for i in range(0, 3 * K, 3):
    x, y, v = XYV[i:i + 3]
    item[x - 1, y - 1] = v
  dp = np.zeros((C+1,4), dtype=np.int64)
  for i in range(R):
    new_dp = np.zeros((C+1,4), dtype=np.int64)
    
    for k in range(4):
      new_dp[:,0] = np.maximum(new_dp[:,0], dp[:,k])
    dp = new_dp
    for j in range(1,C+1):
      
      for k in range(4):
        new_dp[j,k] = np.maximum(new_dp[j,k],new_dp[j-1,k])
      
      for k in range(2,-1,-1):
        dp[j,k+1] = np.maximum(dp[j,k+1],dp[j,k]+item[i,j-1])
  ans = dp[-1].max()
  return ans

R, C, K = map(int, readline().split())
XYV = np.array(read().split(), np.int64)
print(solve(R,C,K,XYV))

Solution (Python):
import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

@njit((i8, i8, i8, i8[:]), cache=True)
def solve(R,C,K,XYV):
  item = np.zeros((R + 1, C + 1), dtype=np.int64)
  for i in range(0, 3 * K, 3):
    x, y, v = XYV[i:i + 3]
    item[x - 1, y - 1] = v
  dp = np.zeros((C+1,4), dtype=np.int64)
  for i in range(1,R+1):
    new_dp = np.zeros((C+1,4), dtype=np.int64)
    
    for k in range(4):
      new_dp[:,0] = np.maximum(new_dp[:,0], dp[:,k])
    dp = new_dp
    for j in range(1,C+1):
      
      new_dp[j] = np.maximum(new_dp[j],new_dp[j-1])
      
      for k in range(2,-1,-1):
        dp[j,k+1] = np.maximum(dp[j,k+1],dp[j,k]+item[i-1,j-1])
  ans = dp[-1].max()
  return ans

R, C, K = map(int, readline().split())
XYV = np.array(read().split(), np.int64)
print(solve(R,C,K,XYV))

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

@njit((i8, i8, i8, i8[:,:]), cache=True)
def solve(R,C,K,item):
  dp = np.zeros((C+1,4), dtype=np.int64)
  for i in range(1,R+1):
    new_dp = np.zeros((C+1,4), dtype=np.int64)
    
    for k in range(4):
      new_dp[:,0] = np.maximum(new_dp[:,0], dp[:,k])
    dp = new_dp
    for j in range(1,C+1):
      
      new_dp[j] = np.maximum(new_dp[j],new_dp[j-1])
      
      for k in range(2,-1,-1):
        dp[j,k+1] = np.maximum(dp[j,k+1],dp[j,k]+item[i-1][j-1])
  ans = dp[-1].max()
  return ans

R, C, K = map(int, input().split())
item = np.zeros((R,C), dtype=np.int64)
for i in range(K):
  r,c,v = map(int, input().split())
  item[r-1,c-1] = v
print(solve(R,C,K,item))

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

@njit((i8, i8, i8, i8[:,:]), cache=True)
def solve(R,C,K,item):
  dp = np.zeros((C+1,5), dtype=np.int64)
  for i in range(1,R+1):
    new_dp = np.zeros((C+1,4), dtype=np.int64)
    
    for k in range(4):
      new_dp[:,0] = np.maximum(new_dp[:,0], dp[:,k])
    dp = new_dp
    for j in range(1,C+1):
      
      new_dp[j] = np.maximum(new_dp[j],new_dp[j-1])
      
      for k in range(2,-1,-1):
        dp[j,k+1] = np.maximum(dp[j,k+1],dp[j,k]+item[i-1][j-1])
  ans = dp[-1].max()
  return ans

R, C, K = map(int, input().split())
item = np.zeros((R,C), dtype=np.int64)
for i in range(K):
  r,c,v = map(int, input().split())
  item[r-1,c-1] = v
print(solve(R,C,K,item))

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

@njit((i8, i8, i8, i8[:,:]), cache=True)
def solve(R,C,K,item):
  dp = np.zeros((C+1,5), dtype=np.int64)
  for i in range(1,R+1):
    new_dp = np.zeros((C+1,5), dtype=np.int64)
    
    new_dp[:,0] = dp[:,-1]
    
    new_dp[1:,1] = np.maximum(new_dp[1:,1],dp[1:,-1]+item[i-1])
    for j in range(1,C+1):
      
      new_dp[j] = np.maximum(new_dp[j],new_dp[j-1])
      
      for k in range(1,4):
        new_dp[j,k] = max(new_dp[j,k],new_dp[j-1,k-1]+item[i-1,j-1])
    for k in range(4):
      new_dp[:,-1] = np.maximum(new_dp[:,-1],new_dp[:,k])
    dp = new_dp
  ans = dp[-1,-1]
  return ans

R, C, K = map(int, input().split())
item = np.zeros((R,C), dtype=np.int64)
for i in range(K):
  r,c,v = map(int, input().split())
  item[r-1,c-1] = v
print(solve(R,C,K,item))

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

@njit((i8, i8, i8, i8[:,:]), cache=True)
def solve(R,C,K,item):
  dp = np.zeros((5,C+1), dtype=np.int64)
  for i in range(1,R+1):
    new_dp = np.zeros((5,C+1), dtype=np.int64)
    
    new_dp[0] = dp[-1]
    
    new_dp[1][1:] = np.maximum(new_dp[1][1:],dp[-1][1:]+item[i-1])
    for j in range(1,C+1):
      
      new_dp[:,j] = np.maximum(new_dp[:,j],new_dp[:,j-1])
      
      for k in range(1,4):
        new_dp[k,j] = max(new_dp[k,j],new_dp[k-1,j-1]+item[i-1,j-1])
    for k in range(4):
      new_dp[-1] = np.maximum(new_dp[-1],new_dp[k])
    dp = new_dp
  ans = dp[-1,-1]
  return ans

R, C, K = map(int, input().split())
item = np.zeros((R,C), dtype=np.int64)
for i in range(K):
  r,c,v = map(int, input().split())
  item[r-1,c-1] = v
print(solve(R,C,K,item))

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

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

dp0 = [[0 for j in range(C+1)] for i in range(R+1)]
dp1 = [[0 for j in range(C+1)] for i in range(R+1)]
dp2 = [[0 for j in range(C+1)] for i in range(R+1)]
dp3 = [[0 for j in range(C+1)] for i in range(R+1)]
for i in range(R):
    for j in range(C):
        dp3[i][j] = max(dp3[i][j], dp2[i][j]+I[i][j])
        dp2[i][j] = max(dp2[i][j], dp1[i][j]+I[i][j])
        dp1[i][j] = max(dp1[i][j], dp0[i][j]+I[i][j])
        dp0[i+1][j] = max(dp0[i+1][j], dp0[i][j], dp1[i]
                          [j], dp2[i][j], dp3[i][j])
        dp0[i][j+1] = max(dp0[i][j+1], dp0[i][j])
        dp1[i][j+1] = max(dp1[i][j+1], dp1[i][j])
        dp2[i][j+1] = max(dp2[i][j+1], dp2[i][j])
        dp3[i][j+1] = max(dp3[i][j+1], dp3[i][j])




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

Solution (Python):
import sys
input = sys.stdin.readline

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

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

dp0 = [[0 for j in range(C+1)] for i in range(R+1)]
dp1 = [[0 for j in range(C+1)] for i in range(R+1)]
dp2 = [[0 for j in range(C+1)] for i in range(R+1)]
dp3 = [[0 for j in range(C+1)] for i in range(R+1)]
for i in range(R):
    for j in range(C):
        dp3[i][j] = max(dp3[i][j], dp2[i][j]+I[i][j])
        dp2[i][j] = max(dp2[i][j], dp1[i][j]+I[i][j])
        dp1[i][j] = max(dp1[i][j], dp0[i][j]+I[i][j])
        dp0[i+1][j] = max(dp0[i+1][j], dp0[i][j], dp1[i]
                          [j], dp2[i][j], dp3[i][j])
        dp0[i][j+1] = max(dp0[i][j+1], dp0[i][j])
        dp1[i][j+1] = max(dp1[i][j+1], dp1[i][j])
        dp2[i][j+1] = max(dp2[i][j+1], dp2[i][j])
        dp3[i][j+1] = max(dp3[i][j+1], dp3[i][j])




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

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

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

@njit(i8(i8[:,:],i8,i8), cache = True)
def solve(item,R,C):
    dp = np.zeros((R+1,C+1,4),np.int64)
    for ri in range(R):
        for ci in range(C):
            dp[ri+1][ci+1][0] = max(dp[ri+1][ci][0], dp[ri][ci+1][3])
            dp[ri+1][ci+1][1] = max(dp[ri+1][ci][1], dp[ri+1][ci][0]+item[ri][ci], dp[ri][ci+1][3]+item[ri][ci], dp[ri+1][ci+1][0])
            dp[ri+1][ci+1][2] = max(dp[ri+1][ci][2], dp[ri+1][ci][1]+item[ri][ci], dp[ri+1][ci+1][1])
            dp[ri+1][ci+1][3] = max(dp[ri+1][ci][3], dp[ri+1][ci][2]+item[ri][ci], dp[ri+1][ci+1][2])
        

    return dp[-1][-1][3]

print(solve(item,R,C))

Solution (Python):
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)