宝石阵法

题目描述

魔法阵是一个$n \times m$的格子（高$n$，宽$m$），$n \times m$为偶数。佳佳手中有$n \times m$个宝石（以$1$~$n \times m$编号）。佳佳从最右上角的格子开始走，从一个格子可以走到上、下、左、右$4$个相邻的格子，但不能走出边界。每个格子必须且仅能到过$1$次，这样佳佳一共走了$n \times m$个格子停止（随便停哪里）。佳佳每进入一个格子，就在该格子里放入一颗宝石。他是按顺序放的，也就是说——第$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 |a-c| + k_{2} \times |b-d|$。

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

输入格式

只有一行用空格隔开的$4$个整数，分别是$n$，$m$，$k_{1}$，$k_{2}$。

输出格式

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

数据范围与提示

对于$100\%$的数据，$1 \leq n \times m \leq 50$，$0 < k_{1},k_{2} \leq 32767$。

样例

2 2 2 2

4