가넷 가족의 집
면접 대비시간 제한1초메모리 제한1024 MB
n×m 격자에 표시된 두 칸 중 정확히 하나만 포함하는 가장 큰 축 정렬 직사각형의 넓이를 구합니다.
문제
가넷 가족이 최근 새 도시로 이사했다. 그들이 사들인 대지는 셜록 홈즈와 왓슨 박사가 사는 집 바로 옆에 있다. 가넷 가족은 이웃이 생겨 반가워하는데, 이상하고 설명하기 어려운 일이 생기면 그 유명한 탐정에게 자문을 구할 수 있기 때문이다.
하지만 지금 가넷 가족이 겪는 문제에는 수수께끼가 없다. 그들이 집을 지으려는 대지는 미터 크기의 직사각형이다. 가넷 가족은 영국인답게 질서를 좋아한다. 그래서 집도 직사각형이고, 벽은 대지의 변과 평행하며, 집의 각 벽에서 그와 평행한 대지 경계까지의 거리가 정수 미터이기를 원한다. 또한 집의 면적은 최대가 되기를 바란다.
한 가지 걸림돌이 있다. 집의 경계가 대지 전체의 경계와 일치할 수는 없다. 대지에는 물이 나오는 우물이 두 개 있는데, 가넷 가족은 한 우물은 집 안에, 다른 우물은 집 밖에 있기를 원한다. 그들은 이 조건을 만족하는 집이 가질 수 있는 최대 면적을 셜록 홈즈에게 물었다. 그가 답할 수 있도록 도와 달라.
입력
대지를 넓이가 1인 단위 정사각형 개로 나눈다고 하자. 각 우물은 정확히 한 정사각형 안에 있으며, 그 정사각형을 완전히 차지한다. 두 우물은 서로 다른 정사각형에 있다. 집의 꼭짓점은 정사각형의 꼭짓점과 일치한다.
첫 줄에는 대지의 크기를 나타내는 두 정수 과 이 주어진다 (). 이어지는 개의 줄에는 각각 개의 수가 주어지며, 단위 정사각형을 나타낸다. 우물이 있는 정사각형이면 1, 아니면 0이다. 대지에는 우물이 정확히 두 개 있다고 보장된다. 즉, 정확히 두 수가 1이다.
출력
가넷 가족의 모든 요구 조건을 만족하는 집의 최대 면적을 한 줄에 출력한다.