andMcolumns. The rows are numbered from 1 toNfrom top to bottom, and the columns are numbered

from 1 to Mfrom left to right. Each cell in the grid has unlimited store of a certain type of sugar, each

unit of sugar gives the player a specic score. The game is just 1 step, given 1 super ant, position it in

any cell in the grid, and the ant will do its magical work to determine your score.

Once a super ant is placed in one of the cells, it does a systematic behavior to gather sugar units from

the stores. If there is no remaining time, the ant gets 1 unit of sugar from the store of its cell and stops

working. If there is some remaining time, it starts a magical operation, which is the ants cloning operation.

The super ant starts to clone itself to all the possible cells according to the current remaining time (all of

its cloning operations start at the same time). It takes Dseconds to clone itself to a cell that is far with

Dunits. An ant at position (R1, C1) is far from the position (R2, C2) by max(|R1- R2|, |C1- C2|) units

(where |X| means the absolute value of X). Once a new super ant is cloned, it behaves as a super ant

by utilizing the remaining time.

At the end, when the remaining time is not enough for any ant to clone itself to any other cell, each ant

will collect one unit of sugar from its cell and your score is the sum of the values of all the collected sugar

units. Note that an ant can not clone itself to another cell with distance more than the current remaining

time, and an ant can not clone itself to the same cell more than once, and it can not clone itself to its

cell, and any cell can contain any number of ants at any time.

Okay, which positions an ant can clone itself to them? First of all, an ant can not clone itself to a cell

outside of the grid. Second, it can only clone to any cell in one of its 8 directions' vectors. Direction

vector means all consecutive cells on the same direction, for example from position (A, B), east vector

will generate (A, B+ 1), (A, B+ 2), (A, B+ 3) and so on. In the below image, a super ant with 2

seconds remaining, can clone itself to 16 positions, 8 of them with distance 1 and 8 with distance 2.

Given the score value of each sugar unit in the grid, the total allowed time you have (the time starts once

the rst ant is placed) and a cell which the rst super ant will start from it, can you write a program

which calculates the score you will get if you used that cell?