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_1,
left_2, or
up. By command
left_1 Ralph moves to the adjacent left cell, by command
left_2 – through one cell to the left, on command & nbsp;
up - to the next cell above. The square is bounded by outer walls. There can also be internal walls between adjacent square cells. Ralph cannot go through walls. Ralph can't go outside the labyrinth either.
Each cell of the maze contains an integer. Getting into each cell, Ralph updates his score by the value of the number written in the cell in which he falls. Moreover, if the number written in the cell is positive, then Ralph's score increases, if negative, it decreases. Ralph's starting score is written in the starting square.
Determine the maximum and minimum score that Ralph will have when moving from the lower right cell of the labyrinth (starting cell) to the upper left.
Answer two numbers – first the maximum number, then the minimum. Both numbers are specified on the same line, separated by one space.
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.