P1585 Magic Grid

A magic grid is an $n \times m$ grid (height $n$, width $m$), where $n \times m$ is even. Smart has $n \times m$ gems (numbered $1 \sim n \times m$). Smart starts from the top-right cell. From a cell, he can move to the $4$ adjacent cells up, down, left, and right, but he cannot go out of bounds. Each cell must be visited exactly once, so Smart visits $n \times m$ cells in total and stops anywhere. Every time Smart enters a cell, he places one gem in that cell. He places them in order; that is, the $i$-th visited cell receives gem $i$. If two gems have the same value when their indices are taken modulo $\frac{n \times m}{2}$, then these two gems have a subtle influence on each other. In other words, by taking gem indices modulo $\frac{n \times m}{2}$, we partition the gems into $\frac{n \times m}{2}$ pairs, each containing exactly two gems. For each pair of gems, suppose the first gem is at row $a$, column $b$, and the other is at row $c$, column $d$. Then the influence value of these two gems is defined as $k_1 \times \lvert a - c \rvert + k_2 \times \lvert b - d \rvert$. You need to find, among all valid placement schemes, the minimum possible value of the maximum influence among all paired gems. In other words, if we define the influence value of the pair with remainder $i$ modulo $\frac{n \times m}{2}$ as $a_i$, you need to find the minimum possible value of $\max \{ a_i : i=0,1,2,\ldots \}$.

One line containing four integers separated by spaces: n, m, k1, k2.

Output a single integer: the required minimum possible value of the maximum influence among all paired gems.

For $100\%$ of the testdata, $n \times m \le 50$, $1 \le k_1, k_2 \le 32767$. Translated by ChatGPT 5