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 two commands:
right or
down. On command
to the right Ralph moves to the neighboring right cell, on command
down – to the next lower one. 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.
In each cell of the maze, Ralph eats a certain number of pancakes. In the starting cell, he also eats pancakes. The number of pancakes Ralph eats is determined by the rules of the maze. If the number indicated in the cell is a multiple of three, then Ralph eats a third of the indicated number, otherwise, he eats only one pancake.
Determine the maximum and minimum number of pancakes that Ralph will eat by moving from the top left cell (starting cell) to the lower right.
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.