문제

현대백화점에 세로가 칸, 가로가 칸으로 이루어진 주차장이 있다. 주차장의 각 칸에는 대의 차량만 주차할 수 있다.

최근 현대백화점을 이용하는 손님이 증가하면서 주차장이 매우 혼잡하게 되었다. 현대모비스는 이 문제를 해결하기 위해서 특별한 주차 시스템을 만들어, 모든 자동차가 효율적으로 주차할 수 있도록 하였다. 주차 시스템은 다음과 같은 방식으로 작동된다.

주차 시스템은 주차장의 한 칸을 가지로 분류한다. 

• 은 현재 해당 칸에 자동차가 없다는 것을 의미한다.
• 은 현재 해당 칸에 주차한 자동차가 있다는 것을 의미한다.
• 는 현재 해당 칸에 자동차는 없지만, 장애인 전용 주차 공간이다.

주차 시스템은 분류된 정보를 바탕으로 주차장의 상태를 여러 개의 구역으로 분리한다. 이때, 같은 구역에 속한 두 주차 칸 사이에는 항상 상태가 인 칸을 거치지 않고 이동하는 경로가 존재하고, 서로 다른 구역에 속한 두 주차 칸 사이에는 그러한 경로가 존재하지 않도록 주차 구역을 나눈다.

주차 시스템은 마지막으로 각 분할한 구역의 주차 분류의 상태에 따라서 점수를 측정한다. 주차 구역에 존재하는 상태가 인 칸의 개수마다 점을 더하고, 상태가 인 칸의 개수마다 점을 뺀다. 이렇게 모든 주차 구역에 대해 점수를 측정하고, 이 중 가장 높은 점수를 가지고 있는 구역으로 차를 안내한다.

위의 사진은 크기의 주차장의 현재 모습이다. 위 주차장에서 조건에 따른 구역은 총 개의 구역이 나오게 된다. 각 구역의 점수를 계산하면 다음과 같다.

• 노란색 구역 : 점
• 파란색 구역 : 점
• 초록색 구역 : 점

위 사진의 경우에는 파란색 구역의 점수가 가장 높기 때문에, 을 출력한다. 위 사진처럼 주차장을 여러 개의 구역으로 분리한다. 개 이상의 주차 칸으로 분리된 구역 중, 점수가 가장 높은 주차 구역의 점수를 구하시오. 단, 주차 구역이 존재하지 않거나 음수인 경우에는 을 출력한다.

입력

첫 번째 줄에 주차장의 크기를 나타내는 정수 이 공백을 두고 주어진다. 

두 번째 줄부터 줄에 걸쳐서, 개의 숫자들이 공백을 두고 주어진다. 각 숫자는  만 주어진다. 번째 줄의 번째 수는 주차장의 칸의 상태를 의미한다.

출력 형식

가장 점수가 높은 주차 구역의 점수를 출력하시오. 단, 주차 구역이 존재하지 않거나 음수인 경우에는 을 출력한다.

구름 블로그 방문하기

* 문제에 대한 힌트는 블로그에서 확인할 수 있습니다.

* 문제에 대한 질문은 Q&A에 남겨주세요!