Rakesh has been given a problem in his interview to solve. In the problem, A matrix of size m*n is given. Elements of matrix will be 0,1,2,3 only. He has been given a source position in the first Column of the matrix and he has to reach to the last Column of the matrix. He can move from a position (x,y) to (x-1,y+1) or (x,y+1) or (x+1,y+1) . The elements of the matrix represents value of the coins. If he is at any point he will add its coin value to the total coin value if element value is 0,1 and 2 whereas for 3 he will decrease the total coin value by 3. He has to maximize the total coin value on the way to the last column from source.He has been given one condition that if total coin value is negative at any point of time he will stop moving . Rakesh has been given a magic spell which helps in maximizing the total coin value. This magic spell can be used only once in the path and after using it, for at most 2 column after the current column, instead of decreasing the total coin value by 3 for element 3 he will now increase the total coin value by 3. He has to print the maximum total coin value he can get starting from source to the last column if he couldn't reach to the last column print -1 or if total coin value is negative after reaching to the last column print -1. As he is not able to solve the problem he needs your help.

Constraints:

1<=m<=6

1<=n<=12