{"code":"boardmotion","name":"Đường đi trên lưới","description":"Cho một lưới ô vuông $A$ kích thước $m×n$, các hàng của lưới được đánh số từ $1$ tới $m$ từ trên xuống dưới, các cột của lưới được đánh số từ $1$ tới $n$ từ trái qua phải, trên mỗi ô của lưới ghi một số nguyên. \r\nNgười ta muốn tìm một cách đi từ cột $1$ tới cột $n$ của lưới theo quy tắc: từ một ô chỉ được phép đi sang một trong các ô ở cột bên phải có đỉnh chung với ô đang đứng (không đi ra ngoài lưới). \r\nHãy chỉ ra một cách đi mà tổng các số ghi trên các ô đi qua là **lớn nhất**.\r\n\r\n#### Input \r\n* Dòng đầu gồm 2 số nguyên dương $m,n \\leq 1000$ .\r\n* $m$ dòng tiếp theo, mỗi dòng là $n$ số nguyên có giá trị tuyệt đối không vượt quá $10^6$, số thứ $j$ là số ghi trên ô $(i,j)$ của lưới.\r\n\r\n#### Output\r\n * Dòng 1 : Ghi tổng các số ghi trên các ô đi qua trên đường đi tìm được.\r\n * $n$ dòng tiếp theo mỗi dòng ghi chỉ số hàng và chỉ số cột của một ô đi qua theo đúng thứ tự trên hành trình tìm được.\r\n\r\n#### Example\r\n\r\n!!! question \"Test 1\"\r\n    ???+ \"Input\"\r\n        ```sample\r\n        4 5\r\n        7 2 1 2 6\r\n        1 2 5 4 5\r\n        1 5 3 5 2\r\n        5 2 3 1 1\r\n        ```\r\n    ???+ success \"Output\"\r\n        ```sample\r\n        25\r\n        4 1\r\n        3 2\r\n        2 3\r\n        2 4\r\n        1 5\r\n        ```","points":1000.0,"partial":false,"time_limit":1.0,"memory_limit":1048576,"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}}