The square is lined with
N × N cells (1 < N < 30). The executor Robot can move around the cells, performing one of two commands for one movement:
right or
up. On command
to the right the Robot moves to the adjacent 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 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 bottom left cell to the top right. 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.
Sample input
For the specified input, the answer should be a pair of numbers:
22 34
Assignment file