Papaya Jungle

Bessie has wandered off the farm onto a neighbouring farmer's land, where he grows delicious papaya fruit that cows adore. The papaya jungle is divided into a grid of $R$ rows and $C$ columns ($1 \le R \le 40$, $1 \le C \le 40$). Bessie can move from her current square to any existing adjacent square along the $x$- or $y$-axis (up, down, left, or right). For example, in the diagram below, if Bessie is on the square marked B, she can move to any of the squares marked T:

.T.
TBT
.T.

Bessie always begins by eating the papayas on square $(1, 1)$ (row 1, column 1). After finishing a square, she uses her trusty binoculars to count the fruit remaining on each adjacent square, then moves to the square with the most uneaten fruit. That square is always uniquely determined. Following this rule, Bessie always eventually reaches square $(R, C)$ and eats the fruit there.

Given the size of the papaya jungle and the number of papayas $F_{ij}$ ($1 \le F_{ij} \le 100$) on each square, determine the total number of papayas Bessie eats.

• Line 1: Two space-separated integers $R$ and $C$.
• Lines 2 to $R+1$: Line $i+1$ describes row $i$ of the jungle with $C$ space-separated integers $F_{i1}, F_{i2}, \ldots, F_{iC}$, the number of papayas on each square.

• Line 1: A single integer, the total number of papayas Bessie eats by the time she finishes the fruit on the bottom-right square $(R, C)$.

Bessie eats the papayas in the order given by the letters (a, b, c, …) next to the numbers below, corresponding to the example input above:

3a  3   4g  5h
4b  5c  3f  2i
1   7d  4e  2j

She declines 4 papayas (the 3 on $(1,2)$ and the 1 on $(3,1)$) and eats 39, visiting 10 of the grid's 12 squares.