R행 S열 격자가 있고 격자의 각 칸에는 -1,000,000 이상 1,000,000 이하의 정수가 쓰여 있다.

이 격자에서, 일부 칸을 선택하여 사각형을 만들 수 있다. 사각형들 중 다음 조건을 만족하면 ‘멋진 사각형’이다.

- 왼쪽 위의 칸과 오른쪽 아래 칸을 파란색으로, 왼쪽 아래 칸과 오른쪽 위의 칸을 빨간색으로 칠한다. - 이때, 빨간 칸에 있는 수의 합보다 파란 칸에 있는 수의 합이 더 작거나 같으면 ‘멋진 사각형’이다.

한편, 사각형들 중 다음 조건을 만족하면 ‘아주 멋진 사각형’이라고 부르자.

- 선택한 범위의 부분 사각형 들에서 '멋진 사각형'이 두 개 이상 발견되면 '아주 멋진 사각형'이다.

격자에 들어있는 수가 주어질 때 가장 큰 크기의 ‘아주 멋진 사각형’을 구하는 프로그램을 작성하여라.

아주 멋진 사각형 (NEO) timer 1s memory 128MB

아주 멋진 사각형 (NEO) 1s 128MB