MaxSum (visit all columns by chess knight)
There is a rectangular table with N rows and M columns. There is an integer in each cell. It is necessary to pass it from the top to bottom. You can start from any cell in top row, then you can move as chess knight, but down only, and you should end route in any cell of the bottom row. In other words, from cell (i, j) you can move to (i+1, j-2), or (i+2, j-1), or (i+2, j+1), or (i+1, j+2), excepting cases which lead out of table.
Write a program that will find the greatest possible sum of the values of passed cells among all admissible paths that pass through all columns.
Input
The first line contains N and M - the number of rows and number of columns (1 ≤ N ≤ 42, 1 ≤ M ≤ 17), then each of the N lines contains exactly M space-separated integers (each not exceeding 10^6 by absolute value) - values of table's cells.
Output
Print a single integer - the maximum possible sum among admissible paths that pass through all columns. In case of no admissible path that is formed by knight's moves and passes trough all columns, print line "impossible" without quotes, small Latin characters).
Note: For table 4×3 there are four ways to pass each column with admissible moves:
Maximum sum achieved with third way: 25 = 15 + 4 + 6.
For table 3×3 there aren't admissible ways.