Normal MaxSum#805
The authors of the day propose this challenge: "Consider a rectangular table with rows and columns. Each cell in the table contains an integer. Your task is to traverse the table from top to bottom, starting from any cell in the top row. From each cell , you can move to one of the 'lower neighboring' cells: (i+1, j-1), (i+1, j), or (i+1, j+1). If j = N, only the first two options are available, and if j = 1, only the last two options are available. The route must end in a cell in the bottom row."
Additionally, there is a constraint: the path must pass through every column at least once.
Write a program to determine the maximum possible sum of the values of the cells traversed along any valid path.
The first line contains and , representing the number of rows and columns (2 \le M \le 1024, 2 \le N \le 768, M \ge N). Each of the following lines contains space-separated integers, with each integer not exceeding 10^6 in absolute value, representing the values in the table cells.
Output a single number: the maximum sum achievable.
Example 1