给你一块 M × N 方格的矩形板。此外,您还会获得无限数量的 2 × 1 方格标准多米诺骨牌。您可以旋转棋子。您需要在棋盘上放置尽可能多的多米诺骨牌,以满足以下条件:
1. 每张多米诺骨牌完全覆盖两个方格。
2. 没有两个多米诺骨牌重叠。
3. 每张多米诺骨牌完全位于棋盘内部。允许接触板子的边缘。
查找在这些限制下可以放置的多米诺骨牌的最大数量。
输入
在一行中,您将获得两个整数 M 和 N——以正方形表示的棋盘尺寸 (1 ≤ M ≤ N ≤ 16)。
输出
输出一个数字——最多可以放置的多米诺骨牌数量。
示例
输入 #1
2 4
输出 #1
4
输入 #2
3 3
输出 #2
4