Description

Given non-negative integers $a, b$, there are two operations:

1. Choose any positive integer $x$, subtract $x$ from both numbers. The cost of performing this operation once is $c$.
2. Choose any positive integer $x$, multiply one of the two numbers by $x$, and divide the other by $x$ and then take the floor. The cost of performing this operation once is $d$.

Here, taking the floor means changing a number to the greatest integer that is not greater than it. For example, the floor of $3.5$ is $3$, and the floor of $-0.07$ is $-1$.

The chosen $x$ can be any positive integer. During the operations, $a$ and $b$ may become negative.

You may perform operations on these two numbers any number of times. Find the minimum total cost to turn both $a$ and $b$ into $0$.

Input Format

One line with four integers $a, b, c, d$, separated by spaces, representing the initial values of $a, b$ and the costs of the two operations.

Output Format

One line with one integer, the minimum cost.

9 36 1 3

4

Hint

[Sample Explanation]

First use operation $2$ once, choose $x = 2$, multiply $a$ by $2$, and divide $b$ by $2$, obtaining $a = 18, b = 18$.
Then use operation $1$ once, choose $x = 18$, subtract $18$ from both numbers, obtaining $a = 0, b = 0$.
It can be proven that there is no solution with a smaller total cost than the one above.

For more samples, please get them here.

[Constraints]

This problem uses bundled testdata, in other words, you can get the score of a subtask only if you pass all test points in that subtask.

The special properties are as shown above, where $\surd$ means this special property is guaranteed, and a blank cell means it is not guaranteed.

For all data, $0\leq a,b,c,d \leq 10^9$.

Input Format

One line with four integers $a,b,c,d$.

Output Format

One line with one integer.

Hint

Translated by ChatGPT 5