Ralph, the hero of eight-bit computer games, got into a labyrinth of
N × N cells (1 < N < 30). According to the rules of the maze, Ralph can navigate using three commands:
right,
up , or
jump. On command
to the right Ralph moves to the neighboring right cell, on command
up – to the adjacent upper one, by command
jump Ralph moves to the cell, which is located one to the right and two higher from the current cell (see example). The square is bounded by outer walls. There can also be internal walls between adjacent square cells. Ralph cannot walk through the walls, but he can jump over the
innerwalls of the labyrinth with the
jump command. Ralph can't go outside the labyrinth.
At the initial moment of time, Ralph has a star score equal to the number written in the starting cell. Each cell of the maze contains an integer. When moving from cell to cell, Ralph's score changes to the number that is written in the cell to which he moves. At the same time, if the number is positive, then the score increases, if it is negative, it decreases.
Determine the maximum and minimum star scores if Ralph starts from the bottom left cell and ends at the top right.
Answer two numbers – first the maximum number, then the minimum. Both numbers are specified on the same line, separated by one space.
Example of moving Ralph with the command
jump
The source data is a spreadsheet of
N × N, each cell of which corresponds to a square cell. Inner & nbsp; outer walls are marked with thick lines.