{"code":"24ts10dhvinhnan4","name":"ROBOT MANG QUÀ","description":"Cho một bảng **A** kích thước **n x m** ô, trên mỗi ô ghi một số nguyên dương là số lượng quà mà một con robot cần mang đi. Con robot xuất phát tại một ô **A[i,1]** nào đó của cột **i (1 ≤ i ≤ n)** cần di chuyển sang một ô lân cận của cột **j (1 ≤ j ≤ m)**. Cụ thể, từ ô **A[i, j]**, con robot chỉ được di chuyển sang một trong ba ô sau: **A[i, j+1], A[i-1, j+1], A[i+1, j+1]** và khi con robot đi qua ô nào thì mang theo toàn bộ lượng quà ở ô đó.\r\n**Yêu cầu:** Hãy tìm đường đi cho con robot từ một ô nào đó của cột **1** đến một ô nào đó của cột **m** để cho tổng lượng quà mà con robot cần mang đi là lớn nhất.\r\n## Dữ liệu vào\r\n- Dòng một ghi 2 số nguyên **n** và m cách nhau ít nhất một dấu cách **(1 ≤ n, m ≤ 1000)**. \r\n- Dòng thứ **i** trong **n** dòng tiếp theo ghi **m** số nguyên dương, mỗi số không vượt quá $10^{5}$ và hai số liên tiếp cách nhau ít nhất một dấu cách.\r\n## Dữ liệu ra\r\n- Gồm một dòng là tổng các số chứa trong các ô mà con robot đã đi qua.\r\n## Giới hạn\r\n- 50% số test ứng với 1 ≤ n, m ≤ 500; \r\n- 30% số test ứng với 500 < n, m ≤ 800;\r\n- 20% số test ứng với 800 < n, m ≤ 1000.\r\n\r\n## Ví dụ\r\n???+ \"Input\"\r\n\t```sample\r\n    3 5\r\n    7 3 8 1 5\r\n    8 8 3 14 1\r\n    6 15 19 1 1\r\n\t```\r\n???+ success \"Output\"\r\n\t```sample\r\n\t61\r\n\t```","points":100.0,"partial":false,"time_limit":1.0,"memory_limit":262144,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}