Maximum Non-Adjacent Sum in a Grid

You are given a matrix of size \(N \times M\) filled with non-negative integers. Your task is to select a subset of numbers from the matrix such that no two selected numbers are adjacent. Two numbers are considered adjacent if one is located in any of the 8 neighboring cells of the other.

In other words, if a cell \((i, j)\) is selected, then none of the cells \((i+\delta_i, j+\delta_j)\) where \(\delta_i,\delta_j \in \{-1, 0, 1\}\) (except \((0,0)\)) can be selected.

Your goal is to maximize the sum of the selected numbers. Formally, if you denote the set of chosen cell indices by \(S\), then for every two distinct \((i_1, j_1), (i_2, j_2) \in S\) it must hold that \(|i_1-i_2|>1 \text{ or } |j_1-j_2|>1\) (i.e. they must not be adjacent in the 8 directions).

Note: It is guaranteed that all numbers in the matrix are non-negative.

inputFormat

The first line of input contains two integers \(N\) and \(M\) representing the number of rows and columns in the matrix, respectively.

Each of the following \(N\) lines contains \(M\) non-negative integers separated by spaces, representing the matrix.

outputFormat

Output a single integer: the maximum sum that can be obtained by selecting a subset of numbers such that no two of them are adjacent (in any of the 8 directions).

sample

2 2
1 2
3 4

4