题目描述

魔法阵是一个 $n \times m$ 的格子（高 $n$，宽 $m$），$n \times m$ 为偶数。Smart 手中有 $n \times m$ 个宝石（以 $1 \sim n \times m$ 编号）。Smart 从最右上角的格子开始走，从一个格子可以走到上、下、左、右 $4$ 个相邻的格子，但不能走出边界。每个格子必须且仅能到过 $1$ 次，这样 Smart 一共走了 $n \times m$ 个格子停止（随便停哪里）。Smart 每进入一个格子，就在该格子里放入一颗宝石。他是按顺序放的，也就是说——第 $i$ 个进入的格子放入 $i$ 号宝石。

如果两颗宝石的编号对 $\frac{n \times m}{2}$ 取模的值相同，则认为这两颗宝石相互之间有微妙的影响。也就是说，我们按照宝石的编号对 $\frac{n \times m}{2}$ 取模的值，将宝石分成 $\frac{n \times m}{2}$ 对，其中每对都恰有两颗宝石。对于每一对宝石，设第一颗宝石在第 $a$ 行第 $b$ 列，另一颗宝石在第 $c$ 行第 $d$ 列，那么定义这 $2$ 个宝石的魔力影响值为 $k_1 \times \lvert a - c \rvert + k_2 \times \lvert b - d \rvert$。

需要你求出的是，在所有合乎题意的宝石摆放方案中，所有成对的宝石间的最大魔力影响值的最小值为多少。换句话说，如果我们定义对 $\frac{n \times m}{2}$ 取模的值为 $i$ 的一对宝石的魔力影响值为 $a_i$。你需要求出的就是 $\max \{ a_i : i=0,1,2,\ldots \}$ 的最小值。

输入格式

只有一行用空格隔开的四个整数，分别是 $n, m, k_1, k_2$。

输出格式

只需输出一个整数，即题目所要求的“所有成对的宝石间的最大魔力影响值的最小值”。

2 2 2 2

4

提示

对于 $100\%$ 的数据，$n \times m \le 50$，$1 \le k_1, k_2 \le 32767$。