시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 128 MB 86 29 24 34.783%

문제

홍준이는 모의고사 3번에 답이 잘 나오지 않아 디버깅을 하던 중 프로그램 메모리에 상주하는 ‘스퀘어 킬러’라 불리는 버그가 있다는 것을 발견했다. 프로그램 메모리는 0 또는 1로 구성된 R*C 행렬이고, ‘스퀘어 킬러’는 이 메모리 상에 부분정방행렬(정방행렬이란 행과 열의 개수가 같은 행렬을 의미한다. 즉 부분정방행렬이란 정방행렬이면서 그 행렬에 포함되는 어떤 행렬을 의미한다.)로 존재한다. 이 ‘스퀘어 킬러’는 특징이 있는데 이는 이 부분행렬을 180도로 회전시킨 것과 원래 부분행렬이 정확히 일치한다는 것이다.

홍준이는 크기가 가장 큰 ‘스퀘어 킬러’가 궁금해졌다. 크기가 ‘스퀘어 킬러’의 행 또는 열의 개수를 의미한다. 우리는 홍준이를 도와 가장 크기가 큰 ‘스퀘어 킬러’를 찾자.

입력

첫 번째 줄에 300 이하의 R과 C가 주어진다. 그다음 R개의 줄에 각 행의 열을 나타내는 길이가 C인 문자열이 입력된다.

출력

첫 번째 줄에 가장 큰 킬러의 크기를 출력한다.

예제 입력

3 6
101010
111001
101001

예제 출력

3

힌트

(1,5)-(2,6), (2,4)-(3,5), (1,1)-(3,3) 모두가 킬러이고 이 중 (1,1)-(3,3)이 크기가 3으로 가장 크다.