C1669 [Wannafly冬令营2018Day4]欧拉回路

内存限制:1024 MB 时间限制:5000 ms

题目描述

给出一张 $n$ 行 $m$ 列的网格图($n$ 条水平线,$m$ 条竖直线),要求你给图中的每一条边定向,并且规定每条边允许的通过次数($ \geq 1$),使得最后得到的图存在一条欧拉回路(一条通过所有的边的回路,且每通过条边的次数=允许通过次数),我们要使每条边的通过次数之和最小。

我们本来需要你给出具体的构造方案。如果存在多种方案,输出任意一组即可。

但是现在我们只需要你输出最值即可。

输入格式

一行 $2$ 个数 $n,m(2 \leq n,m \leq 1000)$。

输出

给出一个数 $ans$,表示最小权值和。

样例

样例输入 1

2 2

样例输出 1

4

样例输入 2

3 3

样例输出 2

16

提示