MaxSum (Happy Sum - 1)#5860
You have a rectangular table with rows and 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 , 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, you cannot move to (i+1, j+1), and if j = 1, you cannot move to (i+1, j-1). You finish your path in any cell of the bottom row.
Your task is to write a program that finds the maximum possible happy sum of the values along any valid path. A happy number is a natural number whose decimal representation consists only of the digits and . For example, , , and are happy numbers, while , , , and are not. Note that the sum itself must be a happy number, not the individual numbers in the path.
The first line contains two integers, and (1 \leq N, M \leq 77), representing the number of rows and columns, respectively. Each of the next lines contains space-separated integers, each in the range 0 \leq a_{ij} \leq 77, representing the values in the table cells.
Output either a single integer (the maximum found among sums along paths of the specified type), or the string impossible (in lowercase, without quotes). The string impossible is output only when there is no path with a happy sum.
Example 1