MaxSum (odd sum)
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). Note that if j=M, the option to move to (i+1, j+1) is unavailable, and if j=1, moving to (i+1, j-1) is not possible. You can finish your path in any cell of the bottom row.
Your task is to write a program that finds the maximum possible odd sum of the values of the cells traversed along any valid path. The sum must be odd, but there are no restrictions on the parity of the individual numbers in the cells.
Input
The first line contains N and M—the number of rows and columns (1 ≤ N, M ≤ 200). Each of the next N lines contains M space-separated integers, each not exceeding 10^6 in absolute value, representing the values of the table cells.
Output
Output a single number, which is the maximum odd sum found, or the word "impossible" (in lowercase Latin letters) if all possible paths result in even sums.
Note: The maximum possible sum is 42 = 15+9+9+9, but since 42 is even, the answer is the maximum odd sum, which is 39 = 15+9+9+6, achieved by the path a[1][2], a[2][1], a[3][1], a[4][1].