The square is lined into NxN cells (1 < N < 17). The Executor Robot can move around the cells by performing one of four commands in one move: right, down, right by 2 , down 2. On a command to the right, the Robot moves to the adjacent right cell, on a command down – to the next lower one. On a command to the right by 2 - to the cell located two cells to the right, and on a command down to 2 - to the cell located two cells below.
The square is bounded by outer walls. There can also be internal walls between adjacent cells of a square. The robot cannot pass through the wall. Before each start of the Robot, in each cell of the square there is a coin with a value from 1 to 100. Having visited the cell, the Robot takes the coin with him; this also applies to the start and end cells of the Robot's route.
Determine the maximum and minimum amounts of money that the Robot can collect by going from the upper left cell to the lower right one. Answer two numbers — first the maximum amount, then the minimum.
The source data is a spreadsheet of size N × N, each cell of which corresponds to a square cell. The inner and outer walls are marked with thick lines.