← 返回题目列表

Codeforces · 142/B

B. 帮助常规

中文机器翻译题面 查看原题

从前,在遥远的王国里,住着首席皇家将军兰斯洛特爵士。他为他的部下感到非常自豪,他喜欢邀请国王来观看演习,这些演习展示了他所负责的小队的战斗技术和战术。但时间一天天过去,有一天,兰斯洛特爵士与仙女教母发生了一场大争执(有传言,这场争执是在将军说教母飞行技术的坏话之后发生的,看来这对仙女教母的伤害很深)。

争论的结果是,教母对将军下了一个相当奇怪的诅咒。听起来很复杂,而且没什么害处:“如果两个士兵之间的平方距离等于5,那么这两个士兵就会互相冲突!”

演习在一个 n × m 的矩形场地上进行,每个士兵被分成 nm 个正方形 1 × 1 的部分。因此,站在方格 (x1, y1) 和 (x2, y2) 上的士兵之间距离的平方正好等于 (x1 - x2)2 + (y1 - y2)2。现在并不是所有的nm小队士兵都能像仙女教母的诅咒之前一样参加演练。当然,除非将军希望士兵互相打斗,甚至更糟……例如,如果他将士兵放在方格(2, 2)中,那么他就不能将士兵放在方格(1, 4)、(3, 4)、(4, 1)和(4, 3)中——它们中的每一个都会与方格(2, 2)中的士兵发生冲突。

你的任务是帮助将军。您将获得演习场地的大小。您需要计算可以同时放置在该场地上的最大士兵数量,以便没有两个士兵受到仙女教母的诅咒。

输入

单行包含空格分隔的整数 n 和 m (1 ≤ n, m ≤ 1000),表示演练练习场的大小。

输出

打印所需的最大战士数量。

示例

输入 #1

2 4

输出 #1

4

输入 #2

3 4

输出 #2

6

注意

在第一个样本测试中,兰斯洛特爵士可以将他的4名士兵放置在2×4的球场上,如下(士兵的位置在方案上用灰色圆圈标记):

在第二个样本测试中,他可以通过以下方式将 6 名士兵放置在 3 × 4 场地上: