U543688 传教士(bishop)

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

一行两个正整数 $n$ 和 $m(1≤n,m≤20)$，代表国土的大小。$n$ 为水平区域数，$m$为垂直区域数。

一行一个正整数，即最多可以安置的传教士的数目。

【样例说明】安置方案如下所示，$X$ 表示为某传教士的据点。 $\begin{array}{cc} X & X & X \\ O & O & O \\ O & O & O \\ X & X & X \end{array}$