{"code":"bodilam","name":"Bố Henry đi làm","description":"Là người Bố đầy trách nhiệm với con cái, nên trước khi đi làm, bố đã cho $Henry$ một bài toán và yêu cầu anh ấy phải hoàn thành trước khi Bố trở về nhà, bài toán như sau:\r\n\r\nCho một bảng có kích thước $n \\times m$ ($n$ hàng và $m$ cột) gồm các ô vuông, và tại mỗi ô vuông chứa một số nguyên. Gọi $S_{k_{i}}$ là tổng giá trị của $k_{i}$ ô vuông đầu tiên của hàng thứ $i$ $(1 \\leq i \\leq n, 0 < k_{i} \\leq m)$ (tính từ trái sang). Nhiệm vụ của $Henry$ là tìm các số $k_{i}$ thỏa mãn 2 điều kiện sau:\r\n\r\n- $k_{1} > k_{2} < k_{3} > k_{4} \\ldots k_{n}$ (các dấu $>, <$ xen kẽ nhau)\r\n\r\n- $Q = \\sum_{i = 1}^{n} S_{k_{i}}$ đạt giá trị lớn nhất.\r\n\r\nNhưng vì không muốn làm khó con mình, nên bố $Henry$ chỉ yêu cầu tìm ra $Q$ là được rồi !\r\n\r\nLà người bạn tốt của $Henry$, hãy giúp anh ấy một tay nhé !\r\n\r\n#### Input\r\n- Dòng thứ nhất chứa 2 số nguyên $n, m$ $(2 \\leq n,m \\leq 1500)$.\r\n- Dòng thứ hai là bảng có kích thước $n \\times m$ gồm các ô có chứa số nguyên. (Các số nguyên này có giá trị tuyệt đối không quá $10000$)\r\n\r\n#### Output\r\n- In ra giá trị $Q$ lớn nhất cần tìm.\r\n#### Example\r\n\r\n!!! question \"Test 1\"\r\n    ???+ \"Input\"\r\n        ```sample\r\n        3 3\r\n        1 2 3\r\n        2 3 1\r\n        1 2 3 \r\n        ```\r\n    ???+ success \"Output\"\r\n        ```sample\r\n        17\r\n        ```\r\n    ??? warning \"Note\"\r\n        Ta sẽ chọn $k_{1} = 3, k_{2} = 2, k_{3} = 3$. Khi đó $Q$ đạt giá trị lớn nhất là $(1 + 2 + 3) + (2 + 3) + (1 + 2 + 3) = 17$\r\n\r\n!!! question \"Test 1\"\r\n    ???+ \"Input\"\r\n        ```sample\r\n        3 3\r\n        1 2 3\r\n        -1 -2 -3\r\n        1 2 3 \r\n        ```\r\n    ???+ success \"Output\"\r\n        ```sample\r\n        11\r\n        ```\r\n    ??? warning \"Note\"\r\n        Ta sẽ chọn $k_{1} = 3, k_{2} = 1, k_{3} = 3$. Khi đó $Q$ đạt giá trị lớn nhất là $(1 + 2 + 3) + (−1) + (1 + 2 + 3) = 11$","points":400.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}}