Description

Bessie has accidentally wandered out of Farmer John’s field and into a neighboring farmer’s land. She picks up a papaya—papayas are a rare delicacy for cows. Like typical fields in Wisconsin, this papaya grove is partitioned into a grid of $R$ rows and $C$ columns ($1 \le R, C \le 40$). Bessie can move from one cell to an adjacent cell along a straight line parallel to the X-axis or Y-axis. She finds herself starting in the papaya grove at $(1, 1)$, the first row and first column, leisurely chewing on a papaya.

Bessie always uses her trusty binoculars to count the number of papayas hanging in each adjacent cell. Then she wanders to the adjacent cell that has the most papayas that have not yet been eaten (this cell is guaranteed to be unique).

Following this movement rule, Bessie will eventually stop at $(R, C)$ and eat the papayas there.

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

Input Format

Line 1: two integers $R$ and $C$ separated by a space.

The next $R$ lines: the $(i + 1)$-th line describes row $i$ of the grove with $C$ space-separated integers $F_{i1}, F_{i2}, \dots, F_{iC}$.

Output Format

Line 1: a single integer, the total number of papayas Bessie eats by the time she finishes at the barn in the bottom-right corner at coordinates $(R, C)$.

3 4 
3 3 4 5 
4 5 3 2 
1 7 4 2 

39 

Hint

Bessie eats the papayas in the following order:

Translated by ChatGPT 5