안전 영역

재난에 대비하기 위해 어떤 지역의 높이 정보를 조사한다. 이 지역은 N x N 격자로 주어지고, 각 칸에는 그 지점의 높이인 자연수가 적혀 있다.

비의 양을 h라고 하면 높이가 h 이하인 모든 칸은 물에 잠긴다. 물에 잠기지 않은 칸들 중 상하좌우로 서로 이어진 칸들의 묶음을 안전 영역이라고 한다. 대각선으로만 닿은 칸들은 이어진 것으로 보지 않는다.

예를 들어 N=5인 지역의 높이가 다음과 같다고 하자.

비의 양이 4이면 높이가 5 이상인 칸만 남고, 안전 영역은 5개가 된다. 비의 양이 6이면 높이가 7 이상인 칸만 남고, 안전 영역은 4개가 된다. 이처럼 비의 양에 따라 안전 영역의 수는 달라진다.

비가 오지 않아 아무 칸도 잠기지 않는 경우도 고려한다. 지역의 높이 정보가 주어졌을 때, 가능한 모든 비의 양에 대해 안전 영역 수의 최댓값을 구하시오.

첫째 줄에 지역의 한 변의 길이 N이 주어진다. N은 2 이상 100 이하의 정수이다.

둘째 줄부터 N개의 줄에는 각 행의 높이 정보가 주어진다. 각 줄에는 N개의 자연수가 공백으로 구분되어 주어지며, 각 높이는 1 이상 100 이하이다.

가능한 모든 비의 양을 고려했을 때, 물에 잠기지 않는 안전 영역 개수의 최댓값을 첫째 줄에 출력한다.

비가 오지 않아 아무 지역도 물에 잠기지 않는 경우도 반드시 고려해야 한다.