MaxSum (visit all columns by chess knight)#5859
You are given a rectangular table with rows and columns. Each cell contains an integer. Your goal is to move from the top to the bottom of the table, starting in any cell of the top row and moving in steps like a chess knight, but only downward (i.e., never to a higher row), finishing in any cell of the bottom row. In other words, from cell , you can move to (i+1, j-2), (i+2, j-1), (i+2, j+1), or (i+1, j+2), provided these moves remain within the bounds of the table.
Among all such admissible paths, you must pass through every column at least once. Find the maximum possible sum of the values along the path. If there is no such path, output impossible.
The first line contains and (1 \leq N \leq 42, 1 \leq M \leq 17). Each of the following lines contains space-separated integers, each not exceeding 10^6 in absolute value, representing the values in the table.
Print a single integer — the maximum possible sum along an admissible path that passes through all columns. If no such path exists, print impossible (without quotes, lowercase Latin letters).
Example 1
Example 2
For a 4 \times 3 table, there are exactly four ways to traverse every column using admissible moves:
a_{1,1} \to a_{2,3} \to a_{4,2}
a_{1,2} \to a_{3,1} \to a_{4,3}
a_{1,2} \to a_{3,3} \to a_{4,1}
a_{1,3} \to a_{2,1} \to a_{4,2}
The maximum sum 25 = 15 + 4 + 6 is achieved with the third path.
For a 3 \times 3 table, there are no admissible paths passing through all columns.