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

"""

import numpy as np
i4 = np.int32
i8 = np.int64


def solve_core(dp, ar, prev, work):
    work[0, 0] = prev[0]
    if ar[0] > 0:
        work[0, 1] = prev[0] + ar[0]
        dp[0] = work[0, 1]
    else:
        work[0, 1] = 0
        dp[0] = work[0, 0]
    work[0, 2] = 0
    work[0, 3] = 0
    for c in range(1, ar.shape[0]):
        work[c, 0] = max(work[c - 1, 0], prev[c])
        if ar[c] > 0:
            work[c, 1] = max(work[c - 1, 1], work[c - 1, 0] + ar[c], prev[c] + ar[c])
            work[c, 2] = max(work[c - 1, 2], work[c - 1, 1] + ar[c])
            work[c, 3] = max(work[c - 1, 3], work[c - 1, 2] + ar[c])
        else:
            work[c, 1] = work[c - 1, 1]
            work[c, 2] = work[c - 1, 2]
            work[c, 3] = work[c - 1, 3]
        dp[c] = max(work[c, 0], work[c, 1], work[c, 2], work[c, 3])


def solve(a):
    dp = np.empty(a.shape[1], i8)
    dp_prev = np.zeros(a.shape[1], i8)
    work = np.empty((a.shape[1], 4), i8)
    for r in range(a.shape[0]):
        solve_core(dp, a[r], dp_prev, work)
        dp, dp_prev = dp_prev, dp
    return dp_prev[a.shape[1] - 1]


def main(file_name):
    stdin = open(file_name)
    R, C, K = [int(x) for x in stdin.readline().split()]
    a = np.zeros((R, C), dtype=i8)
    for i in range(K):
        r, c, v = [int(x) for x in stdin.readline().split()]
        a[r - 1, c - 1] = v
    return solve(a)


def main2():
    ans = main('/dev/stdin')
    print(ans)
"""
import os, sys
p = os.path.dirname(__file__)
pymain = os.path.join(p, "a.out")
if len(sys.argv) == 1:
    import subprocess
    if p == "":
        pymain = "./" + pymain
    subprocess.call(pymain)
else:
    import gzip, base64, stat
    gz = b'H4sIAA5hQF8C/+19C3xTRfbwTZ8BpAkVsTzEgAFaHiWhBdqCmNIGbiTFLi2Iq3hJ05RmTZOa3EBx3RW3rUsMZVlXXdfP/37sru6yr7+uqy7y3+UNLYiKqIgvYH1ASmB5uYAv8p0zMze59zaBwvr/f7/v+22Vzj3nzpw5c+acMzNnpncesNpnpWk0nPSTxs3gEFox1EJgC8NbHotnAVwJ1wd+38gN57IAzpDn4yyK9AIjLaVali+dlStJo3BJmkWRDmP5pFQjSzM5+Y9FkV7j5hQpxxni5ZDXfA/F5nsWK9K1jOjeLGW5NFYu0kSxkabFipRL4xSp1L4M9q+W4WtZu6S0kuWrlOXHn+pPxXp87qqjcFedRZE+zfI9rSr3LSiXxfX+R8/Seay+VHI5kM4pUqkfJnrcdVOKJ3rqJ3jc3mDLhJaSKROmFBcGfIWTCE96lnf23Pnx/k6T8TyQ4fD9uaajm+5ekO968pl23nL7oneCmWcq8F0RK5MN/9py9IuvKeiThiVXXMNp8N1U+DcN/v3ux9O3PuX8246+D64R/vxB0dvjTwt3v1WztnVlu3PQPY+9MOHnw5rXD3zimooW2z0vFVjftl9KLhqoLDcJfjmXHB/OSI7vSkuOL0xB36ZJjh+XAu/ISo5/MQU+O0W9Y1Lgf5OCjjkzOf5iCvzMFPS3pGjX5BT5jSnyv56iX2wp6OxN0V9Civx1Ker9zxT13p2i379MIc+lKeodn54cX50i/3Up8M+l4P+ZFHzmpsAvTMHPzBTyHJaCn+Mp6I9IxX8Kvdqfot7bU9B5MgX/kRT9OCpFvR+l6MdrU+AfSlFvfQo+9fGRR/lTmYLOMcCP4K7jupi/lsq2cxQfYfiFDP9+GsVb2PgljQPNjE41w+cx/BKQwwDMz+hI/n8uk8/iwRYFP2NZvxiGKvFiJqXfyOivYPipjE/eo8TfnoX1DuEO38v4ZBXXs/56boiS/o0Mb1HVy8E4FRDrnePG4dg0hROEJU0+rxAQHX5REDjh23NrxBK3LyDUOQKuYpvXLVaarUsBX7ugRjRPBqzbCbn9LkdTXbDB5gSk2dno8Aui3+EWAzan1Yo0W1qEZpc/4PM6PG5xubDURCj7ipqDotVJqM01mwTB2dLiqHMvNU+C54BbcHocgYAgLm92CW5vg8+KhebUiJOdiALS5iKhSljmrnd54b1bJHwB1VLAur0Bl1+0eazWeTW+WtaQUsouNCcpo5OdHpfDb4U3kwQbNBn+iQ7RBWXrPdVIu0ZExsRGv2+Z4HF5l4iNgsvv9/mr50AbgHmH4PB4fE4oI7hanK5m0e3zkmLmKYLgo1KSOEvGwDzAFVEeWW5brVBrEqw1U4TqOTVFgoe2YwpW4nGxngDEVCI6s9lcmijt9i5hNJJUVePA+irM2Ngi0tjbml3eJl+9i8k4TnFSvIuBYGpS5qIGt7deaHD7A6Lga7CCSJqaVMz1ltQk6D+nzwv5gk7R2uSkki+WJO8LYg2C3+Fd4hIamkSo6j6VolZOojpqgz6X98RVcDPV74L+WuqyNsV7krJR56gXnI6AiBV5lzXNA6GVen30nZjMcCrMcabMRf6gV3Q3uaj+MO2Mc8rYv6p+mCrrB2BH3he1tVevKpLtJZgsXtboEHsoYG/ZNEEf+13NHocTJNuEHF4dIbR1RzPobr2VEYG+uFrZTSGyA6ejFh2xbdK1VAlK417AtwQIJ5wANkHVucxKgR2mHdTdydibLGcvhReV9UKPGkCx5s25CtlZWcMa/C6lw7rKfnCCCoku67wmairFTrDUf6FXAwH3Ei+0rKaYum/f5AZPMNBIpIkOWWVxMJA10TEMnpY4oRKEzJww37sMu3WeKxBscuFLJ83W4AO14RpElwfcKlYHbllocLg9HLAn+jxcg8vXwDUscYkBzkkcO74Avy/5etHV4ha5JleTs3k51+D0+AIurolmBGSTb6mLq3M2NUN2rJSNqU0ON1QKEudmV1QIRYUmbrbdNrNi4UJ4Li6cpATNZgVYysFT+UybYC4sUhZT5KPPwqRCc+JxUuFkslpMh9VlOqSZ8SfEpQOcBTA+Z5PfaZBqCSYtnqsPKYE4+o/+xrJ9GS2OvM8kFOl/GYx6ejw+oeHeykrM46pHL+/HQfnvZkvvs8gcCt83478LPwWyfbjWbIpzEFjLPcLg0AMFabgC/gWD33z2nkyMgDzL4HtJ/gxuA4PFgke0yOWueH1p3OmsxDzv0R8/noURjbdZ/uAQdx+U22GWP+Kj8y2MJZhk06hTMrxZHn1h87ZMNpeTfngZfpp8XSzDF8nn4TJ8sZx+UwI/Wb4OkuGnyPCNMnyZDC/NIxE/XYbPa6b4bNnclsyjZfg0GT5fhk+X4U0yfIYMXyLDy+NWFhleHrfhZfhseXtleK18XSbD95HhF8vwfeXykeH7yfDNMvw1MnyLDN9fhl8hw+fI8CtleJ0Mv0aG18vwT8jwA2T4tTK8fN2zToa/Vr5OlOEHyvDrZfjrZPjNMnyJXD9l+EHyuIEMf70Mf0CGz5Prmww/WK7nMvwQuX3J8ENl+Asy/DD5uubeBP4GGVorww+Xrytl+Bvl+i/Dy9edBhl+hFz/ZfiRcv2X4W+S678Mb5Trvww/Sq7/Mvxouf7L8GPk+i/D58v1X4YvkOu/DH+zXP9l+LFy/Zfhx8n1X4YfL9d/GX6CXP9l+EK5/svwE+X6L8OXyvVfhp8k138ZfoZcnq3HtXw4M3OhgePbN4tpsb1863bttvj72OQ0eBUblQG/dTda4AnhRnzVfTgGP6O+uB1gdI3dewl8BmF0id2bCXwMYXSF3c8R+COE0QV2ryXwewij6+teQ+B9CKPL615B4N0II9vdzQTeijC6uO7FBN6AMLq27moCP48wurRuC4F/hzC6sm4TgX+JMLqwbgOBn0QYXVe3nsCPIIwuq5sj8MMIo6vqPnUR4R8grCftJ/B9CA8g7SewH+Fc0n4Cfwfha0n7CVyH8EDSfgJ/G+HrSPsJPA/hQaT9BL4V4etJ+wk8E+E80n4ClyE8mLSfwJMQHkLaT+CxCA8l7SfwSISHkfYTeAjCN5D2EzgX4eGk/QTui/CNpP1fI5yGsIG0n8BfLAB4BGk/gc8gPJK0n8DHEL6JtJ/AHyFsJO0n8HsIjyLtJ/A+hEeT9hN4N8JjSPsJvBXhfNJ+Am9AuIC0n8DPIzyWtJ/Av0N4HGk/gX+J8HjSfgI/ifAE0n4CP4JwIWk/gR9GeCJp/1ek/xE2kfYT+D6EzaT9BPYjPIm0n8DfQbiItB/g6k2n/Yu5yNsg2k0Yi9qI4IbNYJ2RX0B1C7c1FOpubCOmp7uxEuZSJ2yhN+7mQx/xrZ+cqq61dW5unmfh+M4tHEk6m4eBTV43o9bAfUbyn1UQsHDru4A0fzP+Fq9dTywezLzPJkTEDjes2UZKJcpsJPkf/AdJtlxM50On+C2RW3jNTv6Ni+KAOIVsRkFdfsXNL0N7ueD18/nQp5HvgwB2Zv4GMJpFNKc6f3S1kt/55beXLyifX15bwz94HN0I33G/sXnjWmhtRD8cwb8a1yCfu28HzEXQW76zzfgE81Y724xrMd2E/bMR556Re0DSyHA+H9rCt27R8yEt32khU6SdFj2UthjQeUFKhodomnkz/3KM/jzAh9qM6/BtaJXxOY7WtZ7VZQ9TTuyhvxq7IK1qj4mZttbZBg0fvsvYzIeeMu4lwnpfzORbKwwaGVP7vyZM8aG7jCXiLXxoB9+6GTizchsJL6GTG9CBRW4EheE7rYxBK2GQD/3BeIBWF8zrXpSLKiLD6dpuBZQtfGPlw0Wb8uIVumiFura1hMQOviOgKV9xcT6vs55FkZ7C6p4bhuPB/cYSTteWAVT48FPkBTRB13Z2ACIqjSV8GP4vivzkS6AIHGPTYsFRfHga31Gh50s7xczI0S/w3aHIIUxBZKekwabTqmVtIXM8rGA9a9N6WlFwcHQaNKjnC9EINWljwRuwJhR15BesluWYhqWMJ3Rtn+uxHd8DhWrLHkCUYjPO3vkw7SgepWSEFxt/D1r1Mg5V5n2RImxP64UYFZGsr8Z+FVegbbSb0vnOCqpAFahAFax/KiQFep8Pf4+L7LsQi9lCO/kOqp6oSk/IVBQ5pqr1FE3bT4gj+FYrCHMIluc7rEyaP/sc23ky8mNI7aEXiCKinoHUbeFbbB2zWb57yftYxP05lfoaSepgQRa+4wVSfWTOTdSISMd2iEZL5LdDVV09R4fyq8gDiY2zh+/RbsqPC+OGL5keWTBPaJhRd/tm3QC0HtqhnZY8Zk1ksmgrOGEPRfktX4IfeZff0n0zH6o06nXtm6C0LdRZhb31bQ3a0MnIR1Re0CTavb+8gM35vCo0tSq0TGvryDhoC83WY5HVY6AIaTdQy7O1dmrtofuN+bYtJ9JtrTs00ckJl7KGDy2CtuzQ8qEue/h+IxTJ58MeowlxkDlma/1ao1u9n3QEooGR7nEIbOPDdiPkLUClz+On5QdfwCc9H+awWi1fsMMWOmnbEkuHnrOHLrxM2q2r3DK3A2xE8iA32kr32HWz/27XXLDrZv69qv0TMffWjumfkqn+qfOkxdF0q/ncnI6Mi0i3cU5o2EWkCMxqxRx76Lw9BC+ORa7FXgXOG5FzMHR0MnpRix3ech4lVWQLHeJD92jndIw/Qngm8xk+PN7Ih615oLlornloRvRJ1/YkUcO7QDna37eHvta1oyJ3V2oQuwj8W1BrLz2Lpg0kwDLt0XkNa1BA2vOoYOl0+rhNays9KN4EqoIafJJqcESuwXsi75yLxaI7KCuLiDFr0XA3n6OKvR5TGY+69gbCeYIHs8TDwujdyvECy7ecu0J+Zifnx8T4yT+nclsJGYkF1N+NVPi78/+knugkpp2VRgstBc4xXAWUd/MFW/ktX6TzrV+k6R4KwVyUL92ia1vRDweRZtAomIG3QL77Qc9CdmMLr3v2843oYCKFhPC2TYa4AT51nhngl/2o71hBVDdvJwxpaIV0/Kg0LkZT5MiYcE63+nmYb1vNMXtHvdGCLuQwOqoBKD+wHk1V6Xld248y0AyPxv3ETTcm/IQ9dCTSer3KS4zql9JLnD/HmBzSj46PEcLVXUZDCndBDKqnz1gvWRFfuk33w1hfbA14DFxt2EL/QKfxx89QQDtQ37U4MBHP0YhIsF4QaQEfcmv5jowPSXWaCB8qpy7ESLzOeVqwg9ej4PNBAbXECOOuZJQ95JL8B3Ed96Pr6JS5jvcJ/4CO/GkMsrUda25kfiMf/cZfGXeQLcMIboNnrWuHcftA3G3YO4rz5G7jNXAbp3nNAXAbp6EPidv4J3EbL59Ft9GJbiMGbvEQjiwrsadDxkNINDzMiI4D5HIQHcd7n9HhcSUxD2iJpO7lZ/EFsGYPlfChRnQcRB753bnAgu7GFVSLPUaDwoFMkJ6IP9W1Pav2Iib0IrUaZp8yKx5HiYEZ3x5dJNFH+z/Tw37zL2m/PzyD9ktmkow/mRV/5wy14rozSq9C2W3/lsq1jI4zNS+6kPq3/Cvl5/zpS/Dz3mnKz77TV+hVfnGaepWfnVZ4FabpYQsMQRfsYWrMOBlFI9O1jc1GoW7ht3wO/uZzDTF53UMDEdt6AbqrLz6Fp8Zt6wGQj4Yv3alr60Pe3K7lS7fq2r7KQgCG2I65YMrnHujHp4Nn0q38GvHT8LHjDD52+OH1vu8DS7XGvKhuDUl5zX7dyuP4unS/ruNjfNA9u5vXvMaHVzGHlXEa269FBxLTtS+FaUXkT6doe38LaXc9YGRu75kzzKNkkObtsIdFY55kEWh+2sgkIq5tOCfdadWSOSabaxI/SBwqWHzkvZNoPttlxHmJOB5qsocMcl9qA+fCPKmsxCCpRDCLTGQIO+hOthzNJPzbQtnlO2drOVvnbEIGnSAaIMB5VK/uN7ZwutX+dCy/lc4rwfHYQ3vhuQQ9hdX8PvbuCmLZ3fZQrTE/alqD4/1K0oJuO4g63w5SNNlat2ns6SJachTUyT7tLuiftqJ0qi6L+VZoC7qlPL59l271zzOR4utVoU+BiC30gT10ALpniy1cBaz05cOP0i4KZ2yFJn6/EPH8hri2wFBWulu36ncZ6E+32EK3aqPXyuZbts6ZZGpsC11jxMobmceH9ual6VadwJAr6ZbwNcaoFewtfO9ePrz8AB+69xQfWn6BD99xmC89w+vs+/nSLyB5hw8N5kvfg6c3baGB24m2tm4x8KUww9G1/QchdW+XLVy7A7WN11Xt50PfilSFM3ZWAfdr+b9JnNvB85b+U7fqFIo8fBdm/1C36iOA7Jqddg3M95bv5UvPA4XzfOlBqO8s4an0a92qv5FMncDbAb70S8jxJWEVy/+SvILCbmD7Q3j1YffNUFuDJJB4B8AM7VU7DIEmXZt8tajXVLXvwqdyfJLjZtnC5Xp0XjYYs4ImW7gURzdd+YrlWi6ojdz0D6oEodcjLSfIIzg7fUInUFA2MtrFxH5IFFY2PyIV79K17SRLiHLAtf8XPqpod56I0x52QqVr3Q9z8vU7WvFitiTrt+K7UDwzsvIENeTDx1VlcX3ang3i6c4mI0wlVk2m+9eUr3iAlLWfoIuYp3uW3aVr51G0ivkfWfJ+BUs02sT20/hIaOraMB5D6Orad8Bj5BTQ7P4vXM4pnJ8Nnd81acTMYEpPDaWjHAx81wN9eE2XbqUHX4aLtyeGUasevLU99AoZB0jTv0fY7zhOnf2nUWT/XezHAiLo4Egm5Fwq5H5QOCKQRr6Lcn4BCmBXZZN2iEOoXFsr9GTSrxenQJ15sWBDdK5aYkOOU4n5o7GYqlRwN+uZvtgzurYDxFkeiszGrITeIKkBmZFJUcr6WExh4kdmgU2D6ZDWjIPfWDr43aRcnn5xjJY7c4wOU83EV+J+mj10LnIcseHMxyoMQMcC4+YTe/2L6QRyO/iBFd8t4cTMhysqooOQseGkDbBYPLQRAyCxapNu4ylCK/KTbqymMzIOCJo38w9ux+DQneV3lS8qv7tcWLQtkhulWvedY6xxuvbJqGpD4NemnLst3Mb/Bb9e/hp+bcBwa2QLUNx05HZ4oVkILxbDrw1fAU+Rdfji0F3w4p5F8OJV+LUBA7KRH+GL1XfAi7/Cr5eHfxte4HIpshRfNN4pvXgMnjYI+GIRvvjPefDieYw1WBfACwzERyqVL5bMl16MwxczBHixGH69vBt+bbiIpHLxRT8gEDkQUZTds1Aqe1L5YlMNvLgDX+zHFzjljqyKYO/+wYibmRhdOcWiWhcSETSyz0njQMF8GblxNVI9P4xIrFTBE5EXWTCT6FAzDOo7B8aDSkOPKextHK0K5iK5y/puuqcWaPSJUIXD7Buvx0owWh55/iidngJJEx+u1sYp/gxeyOIzDx8jY3HweozvkOaUngS1dAJVWFdHl2AMBoZXWygLZx80Q3ewj05v5WBgiupsoRw+TFttC83S4/MFMoDN0l5KQLbOWQaW0rhcZ7qlzhJfMm0k0t54FK36nK7txYvolgrBioL5WAOhivbQMT2Df7ATwfALGThVaH1NE7kdBBodikb16pGEbPjQP/jQ1sgxlEuHx1iNAQsLWhxP+Ko0VsM0sM2IXMHQFxyISzmLhsV/In8GStHpWLeeLPBXGXHpZSvdvPRaW0EXyWM+Z94XmQNyiw7kZShbaHNkckQh80HdVOYDcUFkoQI/cwQF/kn0TlwDEYHDagd8qUUh7hxpYlBtC5FoCrBvI8u/nq2xAcRkDKsSOtpkFpUZSCyNSrD/9DLmWEKrMuRd1dIEXgYUggqgzViNKfFXtx6h83DMtRAag+LFJUtkwFEq68UIVH4KDU6saEdFaIMzzCeidph/Ktexm8hifQQShpk3CYriQhKG49AIDPlk2VqxJYDR4nSUTUsNdO56jxaz3ESyxIJDbeHpRlsHioZw+9Sn6N2PRh79lKxJ8kDFNp5ygI2ssVuIL592FMeQHQk//h3ISZgm+vMJKmBq8jcz8pM/pc7zBqBmeVHT/TSd+ppPdD/JJsFSR/eN9IG80XSCy3ymRNEb/1lypb3x109S9Ebrp7LeeOljqUqM9x4hPOKiuMbWOssQE6+3tJ0IzsboxAEWRW7p/hOZ18ywdcxiTZ33CTb1fORWSCG/uDd6HWmD3GkUfkLFcORj9D0JcgVRV3c9zPS6f0+8xI64fJuUGcUZdCE3VbGQO/Axpbr3Y9rWA8yVRPVyUiMZKWnTYHyyyHoHI9XOSO2NLyafYrHtFAVrWUE7K9glKyhF2PNphH1EPMJ+Cyt0PSu0XlZo3aVqO/IRLXjwI1pwHSuIM5zxyWLXL35EJzF//EgVu4YJTUn34XSmg3TFrGt/EEMMz2ji2JLu5xJZmgnQ/YL0GpW91QKTnWEsgMvCROVYFwYFIlPJE/qlchYuKM8TR5EnxAKka3tEtmTXteMQ0G0kjhS9XJ4dhj176VnRwuIE+XSqNEI5VXr973Sq1Pl3dYAh2MkIxcMGv8I84WFGfP4pea7IU3DU7iWRjCuovppVz/eieiOpcroxMvTvycMWyWMWJw7Tjv/0sCJmgT2Uk4b9cRK6pPsvGukxIdH7UKI/T/SZlvQZjdljTEWcqIhCzUqEsTcoemYS0llAeob18x2HaT9rI7cdVoaEghvkkaBsUk90NpPhBCrD0UoZXnOYyjDjcFyGlEcmyK09A0DvHqJF3jikDnPPUsWiesXBw4zcDw71moPbWZHbDl1JX444RPty8CFFX3pwhWHVk7VGCdqUcgUUZnV9fJCsycDs8uyhr+O7OnsO0tfbD8pWGdn9qS9JysaTBykbjxyUrS8w9vst6II1ie3i1uPgTs/bQhdl8xTvYbp3dzdMT0GvbK07YEjOJ2vGMKESi9zzIQkH0RB06wXd0uG4K4Zig8nQxUN0cA2lU5UMVehxNB1ha/1KE+xf/nB2+UorF801vx8tBI7soYv20EeRlz9kcVXIruXD/XZmaHrsEtpCw/nW7fr4+mXbpg7cz76bMLOTjQmHIjkf0jGr4RAJKcB6eb68wY186Kwt9BUfOrqxHYufhFmmPTyOBMkrMTLV+j1c9v0X6TfcQAG8lQT2gmRrAniGRr57UNr5fIZknEYWzzeQyNZOO3Qcy813bsU5fGT5QbopkRBz9iEWDnuEThaqNBftmi/pJNDK2QvOgm5qMP4PEv5S7x9GJEwrfwrVBGdMGK+3har0qAeNkE0TrC1/OGelFuaTYAUaxn9wSvcjyu3Z8EHaxUNsdBcdidk6rSQIVb7Tquei46zmE9SSvh2dAktIWJbyofciuR+wboISWgxyYT/Z2G67TdptJ+VGKi1Q+wHVYQ7TzgxybE02V/z8QyaNP2SQ4OClt0jtoXqjpSo03Uh6bTUUqerA7U66u1kCM2o7zIzzcYez2h4SjXy0MBEBaYjvb9pDp3gS9gnl20If4OptMXTiF+AeNq4E1Xg5gxoN6qeNsL+D4HGSr4385SsaOtCSdflNGNoLF/HhOdhHuIXwF1KiEoNKPe3zi/eofZ55j9onDf+Rja8ue8Fh3Q/OpdPN1cX2gk/5Djvd5AKJA+OlEV43K4K+rg+pegvJCj3dgXuurV/r/TcQDvnQEdCVZsaGlo6BJJ55Qhxn13wMWTXBgQ/3A3UZpt4f7GT7ICPfY8MlXXcAC9jhMk0q/4Bq0njZRj/ZRerAkHbpG2IRH+pHd4PBD0THsXg/skfYJdI4/m4sBu6gLM6DPg07n0w80B2EanGnCyC2ysnr4RqId9qPgyWsF8n6d1q+rn0gmHYV2GIoYi+4gNvkeDanfTN0e3wH6daOgabEDhJfupvXzX7DrjnF62a+wbfvw6oXistgxfk22Ubyv0sc35zQsM/4ULe94HPxO3zrlguhri2RdBJkPZwtNpv3mc/JBQpMTX/HFpr+lq0z4x1qIDsv8K1bNXzp3uDHoF18wRl7h/+CPXSBLzjFt35eEpjejRlBjxM1BR+vIj42HhMcjIP2MLIl9xEWhXK6H5CjKq1bobX75fFGsNe5IEIG8QjqpRM9AIMDmJsXN7YwnwewQQrhA2wAOF8yPoDBXOaapNM/AJsALgHYxOASgGFdaiGHgG2tOy2gGrAQiuja7wUxV4W+jo5S2uOhSOQdkGynlf6dMdpm6QlxjI0NyP+gNnRUZkOvRF6CEtHtdD92p94OY2y+JBy6xf/YOzEyF6quCo3B4xCoGAttHeO3Ew3B7QdeYfntWSQkSk6T2MB52eLOaw5SAudV8Q56/e2NshAa7hDLvVG7/0tFPCkRAHpov+LFilop0NSEL8hQ9hN8unY+ZPkLgNCv5s2RTe+kiIZNgczRe6WRD9kbuJ9E8QzQlB+RjpA74B/upw74gf0JB4zD5C0H6JEbEPMYKmaDwlXdtp+6qtlYXWYUxzeyro1kZdFIPcybLbQUPsMEEt0AKUr4gbz5kb776Zi8DxrTsEZxXi0PPOeK7+fDkDuZLEfO86Ev+fD3TWRA7ZOuOnG0Zb807t6UrhjS1r9DHdHYVEOaepTCreATZHy1h8bZwrMNZPjBT0vg9p9eoZ9hmAEd3Yh/gxBZs58NVO8rh9SSdxj+5jSy2YbuBtUyZMJQQdlbbJ8tw4iDDg7og3kcJ9BFv7qfnQojHpqO5mPJaD5I95LdqAcHPVThT8h4fATH4x+8JflnK6g3HY7Vh9/IGPkbjTSDmY8DVCT0JlMVGs22l56H/qp/i6rIXW9h4I1JZCZdFkSWvR2LAdw+R8NINuG6I2xlw9ZufssXt/AjdvOa3bqX7tLLA183UJGJJbIze7qNb0rH9iJNb/U8sRftL9sfM5/Y+BCOuyDIcjzcgbXvJ1P4YiOJFO4i2j5fa5u2QAsLuPZ94iRbeAo5UXb4TcL2o9tI1CPYPzqyYY35fRYCIRIQS9reF+dFl/5ZQ7McW6MIgdz2JlXd2W8m7IZKrktpYKPfpNIbDmnb+8HRkgTb//Z1igizuA9KPLgdLUDmUZL6CNu+FF7FtE+KUh95g+lYZ6QfmcLUWbjoEPpud+KdACahjIZNAPmjXXciYNhHgwr5b5EDE/FIy/o3MCh2IlgbfUCO/gWgoxYsS0QyJaFM1++j4tBBGh2OOWDeMYhm08kkF3w7eoA63dFKp7v/Dep0X3tDWhrQ8Qu5e/hN+Z5W+YKaaljD8GGBLMyyiRsTi2zhu0sQrqVurUrh1lreoG6t+Q0cd2aRkSo6VpFlPstSRbNY6ByN0Az+AR5MssomAowHIsRqGg+yxeNBExmVbErFkKSi43tplk/2kiwmVhE5YPEcPOhlFWnxTw3uLL97m4LC7xiFX1IKdBxnGRvW1KBL7cwmofbWTm3Ezra06kkXHbqz+569cnH2yD+M5S+W8k9T5o+7c1j44Oj7XbqGFaFPbOEbq8I+GM2jwRHR2ez8CnrEC6+r4ikfiqPs4ZtwpXiSxV2PKuKuuyM7oEh0G1CMr9H//DpV1t+/js0mf/KVWB3K9AP5I4PNEyRWclFqHEyTDXTTwYbsEPBW3FXCFkdeJLi7cBI6zBifpe/Eeagdg/FV4NPIqGfBKS+P2wIG3BYIHSWbAlNASNERuGxrRs+15DUAc/n4e9whuHavYofgs73UURoVuwEwKJS+K94k7QHoyR5AdDAGmvjSQ9D5f3yNbiIU6/TpbN6sZdsDar6T7g5cN9JATpNBW/qPGCkFo+0ZBiybT8PQ90MjOtroIQeicSWv0ZVLPg1AwwQqkvk6DU9gHDJS8qpiL2Awa9oC8ELJ9gEGv8b2AdLpNkBFj20AWAd0VrBVYAU99Ba6G7cBwKcXgkenQMqg/cpXadB+xatEVZ7D7n9wO+oDagzqC7ooyWi//Wp8P+BQ5G97yH4APeRMyevaHyU2qqhiFKviBkijywg52kV9I31fpbF4QGX+2pAQ9/OGXop7154e4n78VZm4d73CKsChatVr1CzqX8MDAxauh/1/xezYSTL0eD+evo9UvsbyzdmjsHcyf0NzWkfmBtnYsXcQB5yH6p4PZehZ/I+R69K7jPliDgh7HRE2GePQrEy4Y02Mbw8wv3EoTmwLmKcp24MzkCzcPRqcdNgrfQUHBQy9Bm9EhTfFNwZbO01hMaMatwQrUep5SG/DbmreJrKu3Rp5D4qDQWjHUCQurDZoyP72K9Jw+tPdZMi0Q4Y8DCSoVqDoARbHtwxXsCPj2sgKKBadQjbr0CsslG8WaolfGL5HtlmolVyBdg/ZoJHiaJESgGHeg3+SuwG/B4O4tj10qo7LZ3tpTBweeR5ru16Oy4z8fDfdq+mPRb61m+oFZMicMJwqHsiqf+nwhOKZsGUl0nYTbQrdTaC6V7Wb6l6JpHvNkSGvUN1Di4hU7aIzpH++ws6n9MLfvrtL8rd7YGa3Af8UK2Ld/S/52527Ff72fFdPf/ur3Qp/2/bKVfnbm3f9a/72mWEJB/CnYb10AF1dPRzAY7tkDqCrU+Fvf7v70v72t13/zf42r4s6Q30X8bd5l/a3xzpl/raqs3f+9sVOWsUfO3v42yc7E/52ytCEuGcO7aW47+jsIe7RXTJx37FT5m+H7aL+9rMu6m9R/22hd3BKZO8YNWiIgZvPd0wYDmlNeehrW+gcBvXwb0i3fJ0eeXYHWdGIBvP7koO1h76wh85Vhk6WxwZ+QMLApR8Gj5H53KL49GZNwiGf3cb+JpX9FapG8df1PX8m1ruWTgyI9W4v5x+Hn53gJjb6mlwTve7vuCc2ub1up89b7yia6PIuDUx0iE5fvcuP3yac2LxcbPR5iwpLJgbcomtCs8N5j2OJK0DwfoeXvXc7JwZFtycwMdDo8LvqBb+robCxuZmr8AU99d4xogG/oWFocHtcBq7WMDbf4fV5lzf5ggGD19HkCgBVV0FZmUSrrIwQKytLUJsOvJeVsc+DlJXJPw8yHb8MMsMwo6wMKvE7RJ9/woz8AgP5MpDhzlrDzYbLlV0EPI2+Cp4uWwS/PwVFBGy4jL+xSvauiMwiTs5/WRn9qM1VNuBKhDr2SmU6KlBmEIRmX8CQv6zR7Ww0uAOGUfcFCwwzDGKjOzBhRsB9nwuIKt9ytom3GWidbp/XAP+TD6bUE+X5V3RnqcsJrZju8XmXjKfcs49wMSQ09rI61AsaiziaqayMfRCKc3uXOjzueoMH7Mfv8BgafH4DZgb6y9xiowE//GQwm8rGfAOt660qQU/1aMAVlL0CWf3PcbSIM/SF//v3UVmI/CthBm/Q4zF4faKB9IkqZyBYB4/cLHRTmIc6Leguv8sBnnMJZzJMv9ngNYweDb+mG+odokPS4m/cnZKmQZGASBwpgigDA2Km185A9Wpw+V1ep6vX/oMUJWqa6Lo7F+UjpoB2HD4uuko17C0XfscyweH3O5ZLFpNaj66S5CLaT25vvavF4PDWs6fpVL2WuMTpVYYJBvuMfOC+2fXf1XVABFkivYds9bo1Xl9DQwCYnCSTTH5BPpVLjWH0eCYi2uLa5eMNVTMS2GbIEReiHYQ4aTwU6r0sGdvMx/W2VDMRJSvE+nW8oXY50ylgkXLSfCWs9CSq6FmwwqQda4537FWJ3fzNiN38/5XY8+GnDgRtKjDcAoSwE4jMvcEmlx88qMfd5BYD0+tdTg9Sya8rACk2OVrAnscZ6goMZYb8XuR3e2l+JO8ogB/s45G+pS5/g8e3zOBsdDnvGfmNm6vU2cJE8P9XYK7xcmTgyE/Iq4CJa8bNVyOvCVcorwn/9+TlqK+/OnlBQYW8qFUTi5Zbs2lGvvDf5KPdXqcnWO9K4qtByDijdnlFA76c8T9nwoqxMD4wU58yOjFAX705gyHPNU8SZttvm1luF4S5grlEyj6Z5J5qu82KX4q0XiafeYrVu9Tt93mbQEy9K1FUIzpQQvW9yl5qlT4zeXnCM2H+LMvOvvfFvoN3p8Oi+P6dhDcz/BqWSvg0Bq9T4fcupvBmFX4dwx9wKL+XfEqib2cpT1P195zXqPJtVuW7TONNCxyeoIuJVM7Xwjolv/HvatUp63vOrqxPMzR92tPsm3AlL8ZieIB35fpYTJvGceshxS+ERCA9jm1/ORazAP7AO7HYo5B2HYjFPoB04eFYzJQO7z+JxfKhfNensdhdkF6AtAXS/COQH/GQtkG+ru5YbC8eX4f0OKR5x2KxLsCXHId6MyA9GYtVQ7oO0ifYRwGlb9Np7pvHaVr0mqHXZGvXaLL1evZ9t1N/icWk74wlz0u/n4d5P4O8UvTEyL7XaHoB6sStqhz9rJy8W3X9lmlXcLcMmTa2yEg+12Zi3wJv+TgWG44Rs5k5+vKcvPIcQ2v66rS0E/ion5mjBYRLesajNavw29sgF/KtNkC3pgk5WvbNOzz93ZLkHW5Ubsey8O5xjtY1MydvZo5hZk5+eY6pNWtVZkfG6vQfpaW15eQTdB7JomXf0gP+Th2NxW6I0709XiceJvrsaM86UWYl8K7lpVhsBHuHb+L3iNxXbSfSzE7HT4inSzKtZjJcDDKdOJzjMlqWWLhyGb8zc0zlOSWzc9ZmtmavyurIXJ3xo/SH0tJvyM0pgabMlPFfjtLD+0Twbo8W/N7k27HYMfwupL7RopZBZY5FJoY/YSUKSZTnWAhvqL+fAJ3V2UAnvzEZb5U5azUK3iqyUvDG2jsQUsOHsdgs0M2M+sbk7d2rVdBMS09Oc6+W3sCC326YDrr1FX6V9Gl5e6Fhs3M2p7dmriJtTdenoQDkLd2cTr/N+QfcqgEbG4o0tsv5IjT2Ag3KjVdGgXKRjjJHW8yPMB6OXzkP0r0sK+D5MNi0i+nuj9Ig4+p0a46hIwMEsCqTzzE9lMXnlLRmV+VY/EQwqu4jtoo+QRtN2Cr57l5M84gGv7hoyP1rMRfT5P7DzJ1N6/8rM/dmVu6zxdynWbk/K+bOZWt/bua+0C59rZg71acDdOrrHP3BqVyHTt89lfu9XrurmHtxgP8HJdxvcs+D6/v56L4/M3PrRuPfT/x2TF8o++cx1wEDY4QTJm5zQe5TJq5t7MjfTuTeHMs/NpF7cULfFwu5XxXmhuG58Iv+lK+BNbp9Gq6uAcpp+sLTPk0ewU/mdgDZHRrdB/25tzTnoDW7M3Sv5nCnM3Wv5HArsnYBZpc28xc53K/6D3+vP7el/6saqa1lD6X1X5fN/STNA2Ca9o1srjVDvymbez6j/9lsblPGz6Hsh1nax7Kh4WDCn2dpf5LNPZi9Q8PKD83TdWdyYwauzOS8E/+Zwf1Het9fZ3C/SX87jb4fwdVyXG1Y86d07pBmKsc9njYTev/9tBFr0rmv0v53nI9L0vn3z79//v2T/GfxMDrPqmbzLdMwy7+F8v/QjyZFujtLCb+lgk8zWPom9OHrab9L34IW51FY+saxdG/YUNl9NpzsW8cl7L00H5O+Zf3PizEf+R5umiX+nW5Sn9YS/+44WSew99I3rY+zj2RL37KWvsF8nar98W91s+8pS/7+sGpeLn1zO/6N52stCrw+16LgW/pTqz6q+i/GaHuqB1jY2ENhiY9TDN6j/79rR/F77FQ/g/IoX6NZOoWls1i6gKUNLF3K0odY+jhLf83Sl1i6k6X7WXqEpedYmsXuExrE0tEsncLSWSxdwNIGli5l6UMsfZylv2bpSyzdydL9LD3C0nMszWL3Cg1i6WiWTmHpLJYuYGkDS5ey9CGWPs7SX7P0JZbuZOl+lh5h6TmWZjH/Ooilo1k6haWzhibXl9kVFWWG/Pl1Qa8YNJQUFheaJpiDBDJ/31xSaCouoFjO6XF4lxiWuvwB3KY0mwrhvwnFiqyFkwyX1Jl08A7SPY1KfFr8fkMlPp0Tk+Iz4vauxGfG7VyJz4r7AyU+O6kdpYOVSvanxPeJ27ES3zdu70p8v7jfU+LBK+Ylw/ePj5NKfE7cXyrxOm5FUrw+fu+jEj+Aa3Ymw+dyuGztib827peV+IFxf6zEJ+77UuIHJfUX6eAtpXsjlPi8uL9V4gdz6+9Nhk/c96XED+2BW0PuWTgdSz7O9ZTDtQyPS3D5zyiG367ClzD8cRV+DsPnq/CLGL5ehfcx/NMq/INkDEroifSN/ccZfo2N4r9iA9XbDC/FvaRv5mdpKF6Kv0n4MoaX4mXSHQFehl9bRvHHGP5nDN88m+KHswnANobnblPyc1Gir6p3XBrFn2L4xxn+gTTsmyHcGf9ixfzityz/mmk0/2o20E5Pp3hDBfN7bJx+l+EPs3YNZfwYMyj90yr6RQSvi8cPpfHZyfBSHFPCP87wm1X4XQx/QIWPMfwpFX5cJsWvU+HvYHgpzindHRBieCnuK90F8FeGT1PhTzK8FN+V7gIYlcXqZXjpToRvMbwUP5buOHiA4dfWKfM/y/AmFf4jhteq8DnZye1xcDbTT5U/HMrwp1T4QoZXry8qs2n/nlL1bw3B9/Rj9zE6i1V0HiL5e/rDVPw/Q/IP4MQkfjVZ/j9n01mv2m/vJHR6+s/Xs6l3UvN/mOHVfJ4ldHr61T7aFPdwpsBP1iKXg7kulb+drk1+3+OCFHR29Md7Q3r689+nyP8KoZ8Y76S7ct5Lkf8fBA9+ifXjRHapydkU+fP6JMdXpMD/DPAD0gZzm1X8/zpF/q4+ye+rTOubPP8NKfDmFHh7CvzSFPjdAxDfc17xU8yfBuMFsy9pvfNsCjpbU+Bv6pccf3MK/LdS4Hf1p/0o3Ssu7XEsT5G/IwV+bb/k947uTJH/QL/k96NO1WH+nvO6/GuoPqjtovia5PR/nAK/NQV+cP8U9/2mwM9IgXf2T34/6n39k9/7+mwKOtv6Uz+gtt/3yf1gQ7gLfiV+bwo6n6TAp+VQOmp55uQkz1+eAv8fKfBbU+CH6pLjJ+ioHnLMXlySPqfI35ECvzYF/mIK/CJ9crxfn/w+25+kyH82BX76gOT42hR4Twr85gHM385T+o29KfKfToHX5ya/Z7gwN/n9xjfnJr83uC43+b3E7bnJ7xN+Izc5P2dyU9wPjLcU0rshBdFR53GZemDMPTFJUJN6oHpiinpgSrj4LnkgWCfYBFehs7kZr4Ps9f55xSTbreWTSgW88LKyed4cehlwr4tXmugdp1dyWOGqykzqRZmigAjtsbKrRi+ZtRjPVfeKqHQ4hApqypUISip6uQaTU6VmU+JUqa1GnEIPEtvm1piEROvwAtCayQKycGneS+qCbo/o9gaK5/q8Lno97eWyYgVTG4JerHdyoNnjFp0e260qBrDqWqcn4E9e3koLBpoxCyDqrVMbfP5lDn+9rVawNjQT1ptvqykResUS6SaJpxI8j+xxe13I1rwEXyTTpRijGeLFL8tcae+Yk/gqdntFAXia10NUntuIltSI9hJBcPvwFm5yxfGVHG/pRX71WaDeFFGdS+pFkSSHny5fKnG06vJ5S5VNqLlCKdVcuZRqrlxKNVclpZorkFLNFUlpwRVKacGVS2lBb5l3+sWAGGxoKHRy9S6/a4k7ILr8gtgExgFOKMAJQr1PWOLx1Tk8Qj0YTkBwBFs4p6+p2eMSXfWFU0tLpybPJDSA7dDD7gII1r+ca/A7mlxCfbCpaTkUkUHkrntFVkGYNa+8yipY51YKYI7C7LnzBSvPkHzlPE6ovGNueZWtAt4pCtcrEeSG4viIe9usWTXWWqG2fKbdKtB7ki0W+X3C5FLmouagaHWyF+z+YcGFf0KhuPRaleEbuOpbQRFvQO55BbyqUtttAvlLOSEYcNWzu5yVLSKXM7Pbnelfq8guxrZYZLcvkyvpTfFrwF3eJWJj/B7wb6qxshuwe7ZWqA/4hEawXo8r6YXYaiZqF0BdiavGXY6mFFeNW1Ul5VdjK8VFb8VOohTSTd1qHlJfna6us+e95Erx13tgGsF6CNRWBFLNbhe7jDvBkVkt/iu79b7CbMXb1gUbKNVtoHlNvnpXkp5I3AaulgV2S09t8GHvwvgKUrV5rNZ5Nb5aVQeXsvvE1fS8y5qSKFeSG+eVufAacjWp2tqrl4s1iRBqqyokB4T9PEUgxICM1NJkqjYPmU9UjZWCxzEJ1popQvWcmiLBo5YLzltqxMlO9MxAATqnSljmrnd5iSNTNRwvUL8q84PxQPbXZdYmZ48Gk9vjlTJFfVVLmUqCanydo15wOgJiErModvqCSSx2rtlEGHfUuZea0d0E3DDUgD0K2HxocYPPqrCLpmQWKaA3Zs6dXm3f02TFKWhMsGLooTuCUAf1saEBvV6x1B5gWfA1CH6Hd4lLaGgSwYzvU8nJxPrriuVfBONhPQyK/gDWQRz+5Tx+sQ0UoKIn/1fV/ybof7+r2eNwuqxNTUnHmwaXr0EtaY+7zik4A0GBzYSvouqp7O9LrUlqXOISA0n6TmX/IIN5c66iZmsyAV9N500hnQd6KgowHKXuP/DWTb6lapsRlrS0CM0uf8DndcBKa7mw1KQaeq+KqakyjbokV0SkzB+CbiX1W5OdHpfDj4PDJDI4wD8YhFzJRjE2/ZE3YL53GfIyzxUINmGZigrIb7r6iYITHKfoss5L1piESuIMkzXOJY86qJkmBYi9Czgf6jFu2OQE1IWXNPm8rLDAeiqRuXhZo0PsaZ9IUaXCSVyhTDST5aJJMYtJrdIwhl56ptTDqfR0ilxhYHmT6KiDFBwqSRulJ1gsu/zNXCHQdxVCn08QHUsYtMQbLMTFdf0Edz1HoEZHoJErrF/uBXo0Ff30DTuCogAEeAfTHgdmZE/NHhGrBG9TCDMQ+E26udDvI1PwQlcjWzo01vsTEBB1OhWBNkqDrgMoDekZ6WBVQJIw6GhyO6G8TyS/aP20LhgnuEJY7ODK8Js6fzWU7bFJcVbpXE0JQwxLcY4vvj/DzqZJ5aXzN7UMYeixZ6nah1KVl87piNK++mXK4zn5c7GYTyovned5giHuYvhM1Xk/6WcuO7uXpjrfd4EhIqxgFmu7VnXObgE7U5emOi94WKs8H5hKfnezs3lSeekc0R4WsP6+iv80VXoPO+snwdJ5o+oBLJ7OJfhPT9L++5hM01TnC/W5yvOFavlJ7W9j5WeqziuyAy/x842ZrIy6/GomkyzV+c7D16vOQabo/5CqfPw8FKugOl21L6BKH1WVl87DVLMjPyOnJi8v/TypKi/tg4rzlOcyU/G/VmV/0r70Clae11+6/nWq8tK+f1cdhZ++TP0vqcpL57qanay/VQXU+rNZVV4699SyhMlXc+n69+FenOxcqnTeIN+TvL1aVXoQ/ulk5aVzDCWe5Pyqyx9j/EvlpXMHFlZ+nYp/tT87L7Mt+XnWSJPSULNU9eplDkFev3SOLeLrXfszVeXj5zKaabJec+nyOary0j7s+nsvXb/0g3/DpZWVl/aDu1j5vMvIbzCr36Q+58DKV/fiHHmyv53J8zN55nDx82fzkvifPnLZqQ/Iof+59tL+e0CK8tc/yvyH5tLl/w/X4vwnAJ0AAA=='
    bin = gzip.decompress(base64.b64decode(gz))
    with open(pymain, "wb") as f:
        f.write(bin)
    os.chmod(pymain, 0o775)

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

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

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

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

    for i in range(R):
        for j in range(C):
            for k in range(4):
                if i > 0:  
                    DP[i,j,0] = max(DP[i,j,0], max(DP[i-1,j]))  
                    DP[i,j,1] = max(DP[i,j,1], max(DP[i-1,j])+item[i,j])  

                if j > 0:  
                    DP[i,j,k] = max(DP[i,j,k], DP[i,j-1,k])  
                    if k >= 1:
                        DP[i,j,k] = max(DP[i,j,k], DP[i,j-1,k-1]+item[i,j])  

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

solve(R, C, K, item)

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

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

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

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

Solution (Python):

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

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):
        v = items[i][j]
        dp1[i][j] = max(dp1[i][j-1], dp1[i-1][j] + v, dp2[i-1][j] + v, dp3[i-1][j] + v)
        dp2[i][j] = max(dp2[i][j-1], dp1[i][j-1] + v)
        dp3[i][j] = max(dp3[i][j-1], dp2[i][j-1] + v)

ans = max(dp1[r][c], dp2[r][c], dp3[r][c])
print(ans)

Solution (Python):

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

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):
        dp1[i][j] = max(dp1[i][j-1], dp1[i-1][j] + items[i][j], dp2[i-1][j] + items[i][j], dp3[i-1][j] + 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(dp1[r][c], dp2[r][c], dp3[r][c])
print(ans)

Solution (Python):

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)

Solution (Python):



def next_line():
    return input()


def next_int():
    return int(input())


def next_int_array_one_line():
    return list(map(int, input().split()))


def next_int_array_multi_lines(size):
    return [int(input()) for _ in range(size)]


def next_str_array(size):
    return [input() for _ in range(size)]


def main():
    r, c, k = map(int, input().split())
    dp = [[[0] * (c+1) for i in range(r+1)] for i in range(4)]
    v = [[0] * (c+1) for i in range(r+1)]
    for i in range(k):
        row, col, val = map(int, input().split())
        v[row][col] = val

    for row in range(1, r + 1):
        for col in range(1, c + 1):
            for num in range(0, 4):
                if num == 0:
                    dp[num][row][col] = dp[3][row-1][col]  
                else:
                    
                    dp[num][row][col] = max(dp[num-1][row][col],  
                                            dp[num][row][col-1],  
                                            dp[3][row-1][col] + \
                                            v[row][col],  
                                            dp[num-1][row][col-1] + \
                                            v[row][col],  
                                            )
    print(dp[3][r][c])


if __name__ == '__main__':
    main()

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