8 - 传教士

某王国的疆土恰好是一个矩形，为了管理方便，国王将整个疆土划分成n×m块大小相同的区域。由于国王非常信教，因此他希望他的子民也能信教爱教，所以他想安排一些传教士到全国各地去传教。但这些传教士的传教形式非常怪异，他们只在自己据点周围特定的区域内传教且领地意识极其强烈（即任意一个传教士的据点都不能在其他传教士的传教区域内，否则就会发生冲突）。现在我们知道传教士的传教区域为以其据点为中心的两条斜对角线上（如图）。现在国王请你帮忙找出一个合理的安置方案，使得可以在全国范围内安置尽可能多的传教士而又不至于任意两个传教士会发出冲突。

（若A为某传教士的据点，则其传教范围为所有标有x的格子。为不产生冲突，则第二个传教士的据点只能放在上图的空格子中。）

输入文件共一行，包含两个正整数n和m（1≤n，m≤10），代表国土的大小，n为水平区域数，m为垂直区域数。

输出文件仅一行，包含一个正整数，即最多可以安置的传教士的数目。

样例安置方案如下图所示，X表示为某传教士的据点。
X  X  X
O O O
O O O
X  X  X

深度搜索