4080. 魔法阵

【题目描述】

        魔法阵是一个 n*m 的格子（高 n，宽 m），n*m 为偶数。魔法师小A手中有 n*m 个宝石（以1~n*m 编号）。

        小A从最右上角坐标为（1，1）的格子开始走，从一个格子可以走到上、下、左、右 4 个相邻的格子，但不能走出边界。每个格子必须且仅能到过 1 次，这样魔法师一共走了 n*m 个格子停止（随便停哪里都可以）。每进入一个格子，就在该格子里放入一颗宝石。他是按顺序放的，也就是说——第 i 个进入的格子放入 i 号宝石。

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

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

【输入格式】

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

【输出格式】

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

【样例输入1】

2 2 2 2

【样例输出1】

4

【样例输入2】

5 10 13301 3664

【样例输出2】

18320

【样例说明】

在此键入。

【数据规模与约定】

对于 100%的数据，n*m<=50，0<k1,k2<=32767。

【来源】

在此键入。