Minimize the Cost to Reduce Two Numbers to Zero

You are given two non‐negative integers \(a\) and \(b\) along with two operation costs \(c\) and \(d\). You can perform the following two operations any number of times (and the numbers may become negative during the operations):

1. Subtraction operation: Choose any positive integer \(x\) and subtract \(x\) from both \(a\) and \(b\). This operation costs \(c\). That is, \[ (a,b) \to (a-x,\; b-x) \quad \text{with cost } c. \]
2. Mixed multiplication/division operation: Choose any positive integer \(x\) and do one of the following:
   • Multiply \(a\) by \(x\) and replace \(b\) by \(\lfloor b/x \rfloor\), or
   • Multiply \(b\) by \(x\) and replace \(a\) by \(\lfloor a/x \rfloor\).
   This operation costs \(d\).

Recall that for any real number \(y\), flooring it means replacing it with the greatest integer less than or equal to \(y\). For example, \(\lfloor 3.5 \rfloor = 3\) and \(\lfloor -0.07 \rfloor = -1\).

Your goal is to convert \(a\) and \(b\) to zero with minimum total cost. It is assumed that you can choose any positive integer \(x\) in each operation.

Hint: A useful strategy is to notice that if \(a\) and \(b\) are different, you can subtract the smaller from both (making one zero) at a cost of \(c\) and then finish off the remaining nonzero number with a suitable mixed operation (costing \(d\)). If they are equal and nonzero, a single subtraction with \(x = a\) gives \((0, 0)\) with cost \(c\); however, it might be cheaper to perform two mixed operations if \(2d . Also, if one of the numbers is already zero, one mixed operation suffices.

inputFormat

The input consists of a single line containing four space‐separated integers: \(a\), \(b\), \(c\), and \(d\). \(a\) and \(b\) are non‐negative integers representing the starting values, while \(c\) and \(d\) are the costs for the subtraction and mixed operations respectively.

outputFormat

Output a single integer — the minimum total cost required to reduce both \(a\) and \(b\) to zero.

sample

0 0 5 5

0