题目描述

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

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

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

输入格式

只有一行用空格隔开的 $\red{4 }$个整数，分别是 $\red{n}$、$\red{m}$、$\red{k1}$、$\red{k2}$。

输出格式

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

样例

输入样例

2 2 2 2

输出样例

2

提示

对于 $\red{100\%}$的数据，$\red{n \times m<=50，}$$\red{0<k1,k2<=32767}$