For an example if i have a M by N matrix then here are the rules which we need to follow for calculating the maximum sum.

1.Each cell contains a value v (v varies from -1 to 99999), if v is -1, then this cell is blocked,and the snake can not go through, otherwise, after the snake visited this cell, you can get v point.

2.The snake can start from any cell along the left border of this ground and travel until it finally stops at one cell in the right border.

3.During this trip, the snake can only go up/down/right, and can visit each cell only once.

Special cases :
a. Even in the left border and right border, the snake can go up and down.
b. When the snake is at the top cell of one column, it can still go up, which demands the player to pay all current points , then the snake will be teleported to the bottom cell of this column and vice versa.


Output the highest score you can get. If the snake can not reach the right side, output -1.