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
up. On command
to the right Ralph moves to the neighboring right cell, on command
up – to the next upper 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 even, then Ralph eats half of the indicated number, otherwise, he eats all the pancakes.
Determine the maximum and minimum number of pancakes that Ralph will eat by moving from the lower left cell (starting cell) to the upper right one.
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.