Maximizing Bear's Path Sum

Given an \( n \times m \) grid where each cell contains an integer, a bear wants to travel from the top‑left corner (\( (0,0) \)) to the bottom‑right corner (\( (n-1,m-1) \)). At each step, the bear can move one cell upward, downward, or rightward. The bear cannot visit the same cell more than once or leave the boundaries of the grid. As the bear moves, it collects the integer from each visited cell. Your task is to determine the maximum sum of integers the bear can collect on a valid path.

inputFormat

The first line contains two integers ( n ) and ( m ) (the number of rows and columns, respectively). Each of the next ( n ) lines contains ( m ) integers representing the grid.

outputFormat

Output a single integer – the maximum sum that can be collected by the bear.

sample

3 3
1 2 3
4 5 6
7 8 9

45