{"problem":{"name":"Non-overlapping Squares","description":{"content":"There is an $N\\times N$ grid, and the cell at the $i$\\-th row from the top and the $j$\\-th column from the left $(1\\leq i,j\\leq N)$ contains the integer $A _ {i,j}$. You are given an integer $M$. When","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc347_f"},"statements":[{"statement_type":"Markdown","content":"There is an $N\\times N$ grid, and the cell at the $i$\\-th row from the top and the $j$\\-th column from the left $(1\\leq i,j\\leq N)$ contains the integer $A _ {i,j}$.\nYou are given an integer $M$. When choosing three non-overlapping $M\\times M$ grids, find the maximum possible sum of the integers written in the chosen grids.\nFormal definition of the problem A $6$\\-tuple of integers $(i _ 1,j _ 1,i _ 2,j _ 2,i _ 3,j _ 3)$ is called a **good $6$\\-tuple** when it satisfies the following three conditions:\n\n*   $1\\leq i _ k\\leq N-M+1\\ (k=1,2,3)$\n*   $1\\leq j _ k\\leq N-M+1\\ (k=1,2,3)$\n*   If $k\\neq l\\ (k,l\\in\\lbrace1,2,3\\rbrace)$, the sets $\\lbrace(i,j)\\mid i _ k\\leq i\\lt i _ k+M\\wedge j _ k\\leq j\\lt j _ k+M\\rbrace$ and $\\lbrace(i,j)\\mid i _ l\\leq i\\lt i _ l+M\\wedge j _ l\\leq j\\lt j _ l+M\\rbrace$ do not intersect.\n\nFind the maximum value of $\\displaystyle \\sum _ {k=1} ^ 3\\sum _ {i=i _ k} ^ {i _ k+M-1}\\sum _ {j=j _ k} ^ {j _ k+M-1}A _ {i,j}$ for a good $6$\\-tuple $(i _ 1,j _ 1,i _ 2,j _ 2,i _ 3,j _ 3)$. It can be shown that a good $6$\\-tuple exists under the constraints of this problem.\n\n## Constraints\n\n*   $2\\leq N\\leq 1000$\n*   $1\\leq M\\leq N/2$\n*   $0\\leq A _ {i,j}\\leq10 ^ 9$\n*   All input values are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$ $M$\n$A _ {1,1}$ $A _ {1,2}$ $\\ldots$ $A _ {1,N}$\n$A _ {2,1}$ $A _ {2,2}$ $\\ldots$ $A _ {2,N}$\n $\\vdots$  $\\ \\vdots$  $\\ddots$  $\\vdots$\n$A _ {N,1}$ $A _ {N,2}$ $\\ldots$ $A _ {N,N}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc347_f","tags":[],"sample_group":[["7 3\n3 1 4 1 5 9 2\n6 5 3 5 8 9 7\n9 3 2 3 8 4 6\n2 6 4 3 3 8 3\n2 7 9 5 0 2 8\n8 4 1 9 7 1 6\n9 3 9 9 3 7 5","154\n\nFrom the given grid, if we choose three $3\\times3$ grids as shown in the figure below (this corresponds to setting $(i _ 1,j _ 1,i _ 2,j _ 2,i _ 3,j _ 3)=(1,5,2,1,5,2)$), the sum of the numbers written in the chosen grids will be $154$.\n![image](https://img.atcoder.jp/abc347/f24ee82455befb7c9af500437f79cde8.png)\nThere is no way to make the sum $155$ or greater while satisfying the conditions in the problem statement, so print $154$."],["7 1\n3 1 4 1 5 9 2\n6 5 3 5 8 9 7\n9 3 2 3 8 4 6\n2 6 4 3 3 8 3\n2 7 9 5 0 2 8\n8 4 1 9 7 1 6\n9 3 9 9 3 7 5","27\n\nThe following choice is optimal.\n![image](https://img.atcoder.jp/abc347/d380b6de908ba5259451d798e7851be3.png)"],["16 4\n74 16 58 32 97 52 43 51 40 58 13 24 65 11 63 29\n98 75 40 77 15 50 83 85 35 46 38 37 56 38 63 55\n95 42 10 70 53 40 25 10 70 32 33 19 52 79 74 58\n33 91 53 11 65 63 78 77 81 46 81 63 11 82 55 62\n39 95 92 69 77 89 14 84 53 78 71 81 66 39 96 29\n74 26 60 55 89 35 32 64 17 26 74 92 84 33 59 82\n23 69 10 95 94 14 58 58 97 95 62 58 72 55 71 43\n93 77 27 87 74 72 91 37 53 80 51 71 37 35 97 46\n81 88 26 79 78 30 53 68 83 28 59 28 74 55 20 86\n93 13 25 19 53 53 17 24 69 14 67 81 10 19 69 90\n88 83 62 92 22 31 27 34 67 48 42 32 68 14 96 87\n44 69 25 48 68 42 53 82 44 42 96 31 13 56 68 83\n63 87 24 75 16 70 63 99 95 10 63 26 56 12 77 49\n94 83 69 95 48 41 40 97 45 61 26 38 83 91 44 31\n43 69 54 64 20 60 17 15 62 25 58 50 59 63 88 70\n72 95 21 28 41 14 77 22 64 78 33 55 67 51 78 40","3295\n\nThe following choice is optimal.\n![image](https://img.atcoder.jp/abc347/592c9536ace6712dd7532131b8da15be.png)"]],"created_at":"2026-03-03 11:01:14"}}