택쌤의 자리배치 timer 2s memory 256MB

정올학원 학생들은 한 명도 빠짐없이 모두 절친한 관계에 있는 밝고 아름다운 친구들이다.

문제는 이 절친함이 모의고사를 치는 중에도 나타난다는 것이다. 이에 택쌤은 모의고사 중에는 서로 대화하지 못하도록 자리배치를 하려고 한다.

정올학원 컴퓨터실은 가로세로 N*M칸으로 나누어져있다. 컴퓨터실에는 모의고사를 보지 않고 워드프로세서나 포토샵 등을 공부하는 다른 학생들도 있다.

따라서, 컴퓨터실에는 모의고사를 볼 수 있는 자리가 정해져 있다. 택쌤은 상하좌우로 인접한 자리에는 한 명의 학생만 앉히려고 한다.

이 때 모의고사를 위해 앉힐 수 있는 학생 수의 최댓값을 구하는 프로그램을 작성하라.