Bessie's Papaya Adventure

Bessie accidentally wanders into a papaya jungle partitioned into an R×C grid. Each cell of the grid contains a certain number of papayas, denoted by \(F_{ij}\) where \(1 \leq F_{ij} \leq 100\). Bessie starts her journey at the top-left cell (row 1, column 1) and enjoys the papayas there. After finishing the papayas in her current cell, she uses her binoculars to inspect the four adjacent cells (up, down, left, right) and always moves to the cell with the highest number of uneaten papayas. It is guaranteed that the cell with the maximum papayas among the adjacent ones is unique. Following this rule, Bessie will eventually end her journey at the bottom-right cell (row R, column C) and eat the papayas there as well.

Your task is to simulate Bessie’s journey and compute the total number of papayas she consumes.

Movement rule:

• From cell \((i,j)\), Bessie can move to any adjacent cell \((i+1,j)\), \((i-1,j)\), \((i,j+1)\), or \((i,j-1)\) if it exists.
• After eating the papayas in the current cell, that cell is considered empty (0 papayas).
• Bessie always moves to the adjacent cell with the highest number of uneaten papayas.
• The journey starts at cell \((1,1)\) and ends when Bessie reaches cell \((R,C)\).

Input constraints:

• \(1 \le R, C \le 40\)
• \(1 \leq F_{ij} \leq 100\) for all cells

Note: It is guaranteed that for each move, the cell with the maximum papayas among the available adjacent cells is unique.

inputFormat

The first line of input contains two space-separated integers \(R\) and \(C\), representing the number of rows and columns in the papaya jungle.

This is followed by \(R\) lines, each containing \(C\) space-separated integers. The \(j\)-th integer in the \(i\)-th line represents \(F_{ij}\), the number of papayas in cell \((i,j)\).

Example:

3 3
3 2 5
1 9 1
4 6 7

outputFormat

Output a single integer which is the total number of papayas Bessie consumes by the time she reaches cell \((R,C)\).

Example:

27

sample

2 2
1 2
3 4

8