P6746 ‘MdOI R3’ Operations

This is the only problem in this contest that has no background story, and that is the background of this problem.

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$.

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.

One line with one integer, the minimum cost.

[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](https://www.luogu.com.cn/paste/fnvd95y2). [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. | Subtask ID | $a=0$ | $b=0$ | $a=b$ | $c=1,d\geq 10^5$ | $c \geq 10^5,d=1$ | Score | | :--------: | :------: | :------: | :--------: | :----------------: | :----------------: | :--: | | $1$ | $\surd$ | $\surd$ | | | | 10 | | $2$ | $\surd$ | | | | | 10 | | $3$ | | | $\surd$ | $\surd$ | | 10 | | $4$ | | | | $\surd$ | | 10 | | $5$ | | | $\surd$ | | $\surd$ | 10 | | $6$ | | | | | $\surd$ | 10 | | $7$ | | | | | | 40 | 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