N행 M열의 2차원 격자 grid가 주어집니다. 격자의 각 칸은 한 변의 길이가 √2인 정사각형이며, 각 칸 안에는 대각선이 하나 그어져 있습니다. 이 대각선은 / 방향(1) 또는 \ 방향(-1) 중 하나입니다.

각 정사각형 칸은 대각선에 의해 동일한 크기의 직각삼각형 두 개로 나뉘며, 당신은 각 칸에서 두 삼각형 중 정확히 하나만 색칠할 수 있습니다. 색칠된 삼각형들은 한 '변'을 공유해야 서로 연결되며, 이렇게 연결된 삼각형들의 집합을 하나의 삼각형 덩어리라고 합니다.

당신의 목표는 격자 전체를 적절히 색칠하여, 연결된 하나의 삼각형 덩어리 중 가능한 가장 큰 덩어리의 넓이를 구하는 것입니다. 각 삼각형의 넓이는 칸을 이루는 정사각형의 면적(2)의 절반인 1입니다. 따라서 덩어리에 포함된 삼각형의 개수가 곧 그 덩어리의 넓이가 됩니다.

격자의 상태를 나타내는 2차원 정수 배열 grid가 매개변수로 주어집니다. 이 격자를 적절히 색칠했을 때, 만들 수 있는 삼각형 덩어리들 중에서 가장 넓이가 큰 덩어리의 넓이를 return 하도록 solution 함수를 완성해 주세요.

제한사항

• 1 ≤ grid의 세로 길이 = N ≤ 200,000
• 1 ≤ grid의 가로 길이 = M ≤ 200,000
• 1 ≤ N × M ≤ 200,000
• grid[i][j]는 -1, 1 중 하나의 값을 가집니다.
• grid[i][j]가 -1이면 \ 방향을 나타내며, 1이면 / 방향을 나타냅니다.

테스트 케이스 구성 안내

아래는 테스트 케이스 구성을 나타냅니다. 각 그룹 내의 테스트 케이스를 모두 통과하면 해당 그룹에 할당된 점수를 획득할 수 있습니다.

입출력 예

입출력 예 설명

입출력 예 #1

격자의 상태는 아래 그림과 같습니다.

각 칸에서 한 개의 삼각형을 적절히 색칠했을 때, '하나로 연결된 삼각형 덩어리' 중 넓이가 가장 큰 경우는 아래 그림에서 색칠된 부분과 같습니다. 이 경우 덩어리의 넓이는 5이므로, 5를 return 해야 합니다.

입출력 예 #2

격자의 상태는 아래 그림과 같습니다.

각 칸에서 한 개의 삼각형을 적절히 색칠했을 때, '하나로 연결된 삼각형 덩어리' 중 넓이가 가장 큰 경우는 아래 그림에서 색칠된 부분과 같습니다. 이 경우 덩어리의 넓이는 4이므로, 4를 return 해야 합니다.

입출력 예 #3

최대 1개의 삼각형을 색칠할 수 있습니다. 삼각형 하나의 넓이인 1을 return 합니다.