30452번 - Server Overload 다국어

문제

The IT team of a SY company manages the sever log data. This log data is organized into an $n \times n$ grid, with each cell storing a number indicating the server access count during a specific time period. The server has recently been overloaded and is at risk of going down. To determine the cause of the server overload, the IT team uses a specialized 1ドル \times 3$ analysis tool to find the sub-grids of $n \times n$ grid that represent the high access counts. The 1ドル \times 3$ analysis tool covers some 1ドル \times 3$ sub-grid (of the $n \times n$ grid) of vertical length of 1ドル$ and of horizontal length of 3ドル$. The tool reports the sum of access counts stored in the cells of the sub-grid that the tool covers. The only limitation is that you can use this analysis tool at most $k$ times and the 1ドル \times 3$ sub-grids covered by the tool should not overlap.

Given an $n \times n$ grid and a positive integer $k,ドル write a program that outputs the maximum of the total sum of access counts stored in cells of the $n \times n$ grid covered by the 1ドル \times 3$ analysis tool, such that the tool is used at most $k$ times and no 1ドル \times 3$ sub-grids covered by the tool overlap.

입력

Your program is to read from standard input. The input starts with a line containing two integers, $n$ and $k$ (3ドル ≤ n ≤ 1,000円,ドル 1ドル ≤ k ≤ 5,000円$), where $n$ represents the size of the grid and $k$ is the maximum number of times that the analysis tool can be used. In the following $n$ lines, access count values of the $n \times n$ grid are given; the $i$-th line contains $n$ access count values (from the first column to the last column) of the $i$-th row of the grid. All these access count values are integers between 1ドル$ and 1ドル,000円,000円,000円$.

출력

Your program is to write to standard output. Print exactly one line. The line should contain the maximum of the total sum of access counts in cells covered by the analysis tool such that the tool can be used at most $k$ times and no 1ドル \times 3$ sub-grids covered by the tool overlap.

제한

힌트