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:
left,
down or
jump. On command
to the left Ralph moves to the adjacent cell to the left, on command
down – to the next lower one, by command
jump Ralph moves to the cell, which is located one to the left and two below 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 top right cell and ends at the bottom left.
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.