Maximum Treasures

You are given an ( N \times M ) grid where each cell contains either (0) or (1). A participant is allowed to start from any non-border cell; that is, a cell with row index ( i ) and column index ( j ) such that (1 \leq i \leq N-2) and (1 \leq j \leq M-2). When starting from a valid cell, if the cell contains a treasure (represented by (1)), it is collected and the participant can move recursively in four directions (up, down, left, right) to adjacent cells—again, only if those cells are non-border and contain treasures. Note that once a treasure is collected from a cell, it cannot be collected again.

Your task is to determine the maximum number of treasures that can be collected by starting from any non-border cell and traversing through connected treasures. The connections are considered only in the four cardinal directions.

Note: The boundaries of the grid (i.e. the first and the last row and column) cannot be used as starting points nor can they be traversed during the DFS search. This can be formally stated as: a cell at position ( (i, j) ) is valid if (1 \leq i \leq N-2) and (1 \leq j \leq M-2).

inputFormat

The first line contains two integers \( N \) and \( M \) representing the dimensions of the grid.

The following \( N \) lines each contain \( M \) space-separated integers (each either \(0\) or \(1\)) describing the grid.

Example:

4 4
0 1 0 1
1 1 1 0
0 1 0 1
1 0 1 0

outputFormat

Output a single integer indicating the maximum number of treasures that can be collected under the described conditions.

4 4
0 1 0 1
1 1 1 0
0 1 0 1
1 0 1 0

3