Magic Gem Arrangement

You are given a magical grid (or magic matrix) with n rows and m columns, where n × m is even. In this grid, there are exactly n × m gems numbered from 1 to n × m. A wizard named Smart starts at the top‐right cell (first row, last column) and walks through the grid. From any cell he can move up, down, left or right (without leaving the grid) and he must visit every cell exactly once. As he enters a cell, he places a gem in that cell. The order of placement is exactly the order in which the cells are visited; that is, the i-th visited cell gets the gem numbered i.

Now, the gems interact with each other in pairs. The pairing is defined by taking the gem numbers modulo n × m/2. In other words, for every remainder r (where 0 ≤ r < n × m/2) the two gems whose numbers give remainder r when divided by n × m/2 form a pair. For each pair, suppose the first gem is placed in cell (a, b) and the other in cell (c, d). Their magic effect value is defined as

[ k_1\times |a-c|+k_2\times |b-d| ]

where k₁ and k₂ are given positive integers.

Your task is to choose a valid Hamiltonian path (starting at the top‐right cell and visiting each cell exactly once) so that if for every pair the magic effect is computed, then the maximum of these n × m/2 values is as small as possible. In other words, if the pairs have effect values \(a_0, a_1, \ldots, a_{n\times m/2-1}\), you need to minimize \(\max\{a_0,a_1,\ldots\}\). Output this minimum possible maximum magic effect value.

Note: It can be shown that by choosing an appropriate Hamiltonian path the answer can be expressed in closed‐form. In fact, after careful analysis one may prove that many cases have an optimal answer achieved by nearly “parallel” traversals so that almost all pairs are placed in cells of the same row or in the same column. For example, when one of n or m is 2 there is a slight twist:

• If n = 1 (and hence m is even) then the answer is \(\frac{m}{2}\,k_2\).
• If m = 1 (and hence n is even) then the answer is \(\frac{n}{2}\,k_1\).
• If n = 2 and m = 2 then the answer is \(k_1+k_2\).
• If n = 2 and m > 2, then by a careful ordering one may achieve an optimal value of
    • if m is even: \(\frac{m}{2}\,k_2\);
    • if m is odd: \(k_1 + \frac{m-1}{2}\,k_2\).
• Similarly, if m = 2 and n > 2 then the answer is
    • if n is even: \(\frac{n}{2}\,k_1\);
    • if n is odd: \(k_2 + \frac{n-1}{2}\,k_1\).
• For grids with both n > 2 and m > 2 (recall that at least one of them is even so that n × m is even), an optimal strategy is to arrange the path so that one of the two complementary halves of the path consists entirely of cells in rows (or columns) that can be matched one‐to‐one. In this case the answer is the minimum of the following two candidates:
    Candidate 1: if m is even, then \(\frac{m}{2}\,k_2\);
    Candidate 2: if n is even, then \(\frac{n}{2}\,k_1\).
  The answer is the minimum candidate available.

Given n, m, k₁, and k₂, compute the minimum possible maximum magic effect value.

inputFormat

The input consists of four space‐separated integers:

n m k1 k2

where

• 1 ≤ n, m ≤ 10⁹ (with n × m even),
• 1 ≤ k1, k2 ≤ 10⁹.

outputFormat

Output a single integer: the minimum possible maximum magic effect value achievable by an appropriate Hamiltonian path.

sample

2 2 1 1

2