#P1585. 魔法阵

魔法阵

题目描述

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

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

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

输入格式

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

输出格式

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

2 2 2 2

4

提示

对于 100%100\% 的数据,n×m50n \times m \le 501k1,k2327671 \le k_1, k_2 \le 32767