농부 창호는 NxN 크기의 격자로 이뤄진 정사각형 밭을 가지고 있다.

격자는 1x1 크기의 정사각형이며 다양한 종류의 곡물이 심어져 있거나, 심어져있지 않기도 한다.

추수 때가 되어서 창호는 일꾼 태현이를 시켜 작물을 거두려고 한다.

그런데 농부 창호는 추수할 때 독특하게 추수하는데, 추수할 때 정사각형 형태로 한번만 추수를 해야 하며,

반드시 곡물이 심어져 있는 영역이여야 한다.

또한 심어진 곡물의 가지 수는 최대 2개이어야 한다.

아래 그림의 첫 번째의 경우 올바르게 추수된 경우이고, 나머지의 경우는 올바르지 못하게 추수된 경우이다.

최근 들어 게으름을 피워 창호에게 많이 혼났던 태현이는 창호에게 신임을 얻고자 최대한 넓은 정사각형 영역을 추수하고자 한다.

태현이가 추수했을 때 가능한 영역의 넓이를 알아보자.

추수 timer 1s memory 128MB

추수 1s 128MB