Maximum Apples Collection

Harry is in a magical orchard represented by an (M \times N) grid. Each cell in the grid is one of the following:

• '1' - an apple tree (contains an apple).
• '0' - an empty cell.
• '#' - a rock which cannot be passed.

Harry can start at any cell that contains an apple tree. From a starting cell, he can move to any of the four adjacent cells (up, down, left, right) if the cell is not a rock and has not been visited before. He collects an apple whenever he visits a cell with an apple tree (i.e. value '1'). Note that empty cells (with '0') do not contribute to his apple count, but they can be traversed to reach other apple trees.

Your task is to help Harry determine the maximum number of apples he can collect starting from any apple tree in the grid.

Formally, given a grid (G) of size (M \times N), you need to compute: [ \text{maxApples} = \max_{(i,j)\ in\ {, \text{positions with } G[i][j] = '1' }} { \text{DFS}(i,j) } ] where (\text{DFS}(i,j)) is the sum of apples collected (each apple tree contributing 1) in a connected component that can be reached from ((i,j)) under the movement restrictions.

Note: You are allowed to traverse through empty cells (with '0') to reach other apple trees.

inputFormat

The first line contains two space-separated integers (M) and (N) representing the number of rows and columns of the grid. Each of the next (M) lines contains a string of length (N) consisting of the characters '1', '0', and '#' without spaces.

outputFormat

Output a single integer representing the maximum number of apples that can be collected.## sample

4 4
1100
0#10
101#
#110

4