Find Longest Diagonal Segment

You are given a matrix with R rows and C columns, where each element is 0, 1, or 2. Find the longest diagonal segment that follows the pattern 1, 2, 0, 2, 0, 2, 0, … (the first element is 1, then 2 and 0 alternate indefinitely) and ends at the matrix boundary. Output the length of this segment.

A segment may start at any element of the matrix, may proceed in any of the four diagonal directions, and must end on an element in the first row, last row, first column, or last column. It is guaranteed that at least one such segment of length at least 2 exists.

输入格式

The first line contains R and C; then R lines follow, each containing C integers (0, 1, or 2). 1≤R,C≤500.

输出格式

Output one integer: the length of the longest segment.

样例 1

输入：

3 4
0 0 1 2
0 2 2 2
2 1 0 1

输出：

3

样例 2

输入：

2 2
1 0
0 2

输出：

2

样例 3

输入：

4 3
2 0 0
0 2 0
0 0 1
2 2 2

输出：

2

样例说明

Example 1: starting from the 1 at row 3, column 4 (1-based) and moving up-left, the path passes 2 and 0 and reaches row 1; the segment [1,2,0] has length 3. Example 2: from the 1 in the top-left corner, moving down-right reaches a 2, length 2. Example 3: from the 1 at row 3, column 3 (1-based), moving up-left gives 2, then 2; the second one is not 0, so that fails; moving down-left reaches the 2 in the last row, length 2.