Description

There is a grid of size $n \times m$, where each cell contains an integer. A little bear starts from the top-left corner of the grid and wants to reach the bottom-right corner. At each step, the bear can move up, down, or right by one cell, but it cannot revisit any cell it has already passed through, nor can it move outside the grid boundaries. The bear collects all the integers in the cells it traverses. Find the maximum sum of integers the bear can collect.

Input Format

The first line contains two positive integers, n and m.
The next n lines each contain m integers, representing the integers in each cell of the grid.

Output Format

A single integer, representing the maximum sum of integers the bear can collect.

3 4
1 -1 3 2
2 -1 4 -1 -2 2 -3 -1

9

Source

CSP2020-J4