문제

스키장은 수많은 연인들이 데이트를 하기 좋은 장소 중 하나다. 특히 크리스마스와 발렌타인 데이에 가장 많은 커플들이 스키를 즐긴다. ICU졸업생 두 분이 설립한 DJ_Koo Resort 스키장에서는 그런 날에는 특별히 커플리프트를 운행한다.

커플리프트는 n명이 같이 탈 수 있게 되어 있으며 특별히 커플들만 리프트를 탈 수 있다. 커플들은 리프트를 타기 위해 m X n 격자상에서 기다리고 있으며 각 커플은 인접한 열에서 기다리고 있다.

문제는 커플 중 한사람이 본의 아니게 더 뒤에 서는 경우가 있다는 것이다. 이런 경우 한사람이 다른 한사람을 기다리게 되고 그 열은 정체되게 된다. 또한 X자 형태로 두 커플이 기다리게 되면 둘중 한 커플은 같이 타는 것을 포기해야만 한다.

자, n명이서 탈 수 있는 커플리프트가 있다. m X n 격자상에 커플리프트를 타기 위해 기다리는 커플들이 있을 때, 최대한 많은 커플을 리프트에 같이 태우는 프로그램을 작성하라.