우리 학교는 다른 학교가 부러워하는 도서실을 가지고 있다. 장서를 다량 보유하고 있을 뿐 아니라 전자도서를 볼 수 있는 컴퓨터도 여러 대 설치되어 있고, 바닥에는 카펫이 깔려있다. 최근 도서실의 가구배치를 새로 하게 되었는데, 가구가 놓여있던 자리에는 얼룩이 져서 아주 보기가 흉하였다. 그래서 3 x 3 크기의 카펫 여러 장으로 얼룩진 부분을 모두 가리기로 하였다.

도서실 바닥에는 1 x 1 타일이 m행 n열 격자 형태로 놓여있고 이 중에서 c개의 타일에 얼룩이 졌다. 카펫을 놓을 때는 카펫의 변이 도서실의 벽과 평행하도록 놓아야 하며 정확히 9개의 타일이 가려지게 놓아야 한다.

예를 들어, 다음 그림과 같이 6 x 11 크기의 도서실의 (4, 3), (6, 5), (3, 6)과 (4, 7) 위치에 얼룩이 있다고 하자. 모든 얼룩을 가리기 위해서는 아래 그림과 같이 최소 2개의 카펫을 배치하여야 한다.

모든 얼룩을 가리기 위하여 배치해야 할 최소 카펫의 수를 구하는 프로그램을 작성하시오.

#3557 upload 21 done 6 how_to_reg 6

얼룩 timer 3s memory 512MB

#3557

얼룩 3s 512MB