MaxSum (visit all columns)
You have a rectangular table with N rows and M columns, where each cell contains an integer. You can traverse the table from top to bottom, starting from any cell in the top row. From each cell at position (i, j), you can move to one of the "lower neighboring" cells: (i+1, j-1), (i+1, j), or (i+1, j+1). However, if j=M, you cannot move to (i+1, j+1), and if j=1, you cannot move to (i+1, j-1). Your path must end in any cell of the bottom row.
Your task is to write a program that determines the maximum possible sum of the values of the cells traversed in a path that passes through each column at least once.
Input
The first line contains two integers, N and M, representing the number of rows and columns, respectively (2 ≤ N ≤ 1024, 2 ≤ M ≤ 768, N ≥ M). Each of the following N lines contains exactly M space-separated integers, each not exceeding 10^6 in absolute value, representing the values in the table cells.
Output
Output a single integer, which is the maximum sum found among all paths that pass through every column at least once.
Note: The correct answer is 28 = 15+5+2+6 because any path with a larger sum does not pass through all columns.
Please note that the input file size is large. In C++, it is advisable not to use cin with synchronization enabled, and in Java, it is advisable not to use Scanner, as this may prevent the program from reading the input data in time.