Maximum Non-Adjacent Grid Sum

Given an \(m \times n\) grid containing positive integers, select numbers from the grid such that any two selected numbers do not share a common edge. The goal is to maximize the total sum of the selected numbers.

Note: Two cells are said to share an edge if they are adjacent horizontally or vertically.

Hint: In a grid, if you color the cells in a chessboard pattern (i.e. black for cells with \(i+j\) even and white for cells with \(i+j\) odd), each color forms an independent set. Thus, the answer is the maximum of the sum of cells on the black positions and the sum of cells on the white positions.

inputFormat

The first line contains two integers (m) and (n), representing the number of rows and columns in the grid respectively. This is followed by (m) lines, each containing (n) positive integers separated by spaces, representing the grid values.

outputFormat

Output a single integer representing the maximum sum obtainable by selecting numbers from the grid such that no two selected numbers are adjacent (sharing a common edge).

sample

1 1
5

5