우리 학교는 다른 학교가 부러워하는 도서실을 가지고 있다.

장서를 다량 보유하고 있을 뿐 아니라 전자도서를 볼 수 있는 컴퓨터도 여러 대 설치되어 있고, 바닥에는 카펫이 깔려있다.

최근 도서실의 가구배치를 새로 하게 되었는데, 가구가 놓여있던 자리에는 얼룩이 져서 아주 보기가 흉하였다.

그래서 새로산 카펫 한 장으로 얼룩진 부분을 가리기로 하였다.

도서실은 직사각형 모양이고, 얼룩진 부분도 모두 직사각형 모양이며, 변은 도서실 벽과 평행하다.

새 카펫은 정사각형이다. 이 정사각형 카펫을 도서실의 벽과 평행하도록 놓는데, 완전히 가려지는 얼룩의 수를 최대화 하고자 한다.

예를 들어, 다음 그림과 같이 얼룩이 위치하고 있다고 하자.

점선으로 표시된 여분의 카펫으로 완전히 가릴 수 있는 얼룩의 최대 수는 4개가 되고, 이러한 카펫의 위치는 유일하지 않을 수 있다.

이러한 카펫으로 완전히 가려지는 최대 얼룩의 수를 구하는 프로그램을 작성하시오.

도서실카펫 timer 2초 memory 256MB

도서실카펫 2초 256MB