410246: GYM103993 A As Fast As Possible

Monocarp plays a new computer game. Each level of this game can be represented as the coordinate axis $$$oX$$$.

To beat the current level, Monocarp's character has to travel from the point $$$0$$$ to the point $$$n$$$. There are two ways to move in the game:

• walk to an adjacent point; it takes $$$a$$$ seconds (i. e. move from $$$x$$$ to $$$x - 1$$$ or $$$x + 1$$$ in $$$a$$$ seconds);
• jump to a point with distance $$$d$$$ from the current one; the leap takes $$$b$$$ seconds (i. e. move from $$$x$$$ to $$$x - d$$$ or $$$x + d$$$ in $$$b$$$ seconds).

Note that it's possible that Monocarp's character will travel through some points that are to the left of point $$$0$$$ or to the right of point $$$n$$$; it's not against the rules, since the level is infinite.

You have to calculate the minimum time required to reach the point $$$n$$$ from the point $$$0$$$.

The first line contains four integers $$$n$$$, $$$a$$$, $$$b$$$ and $$$d$$$ ($$$1 \le n \le 1\,000$$$, $$$1 \le a \le 1\,000$$$, $$$1 \le b \le 1\,000$$$, $$$1 \le d \le n$$$) — the point Monocarp's character has to reach, the time required to walk to an adjacent point, the time required to leap, and the length of the leap.

Print one integer — the minimum time required to reach the point $$$n$$$ from the point $$$0$$$.

9 7 6 5

19

20 5 10 15

35

4 3 5 2

10

In the first example, it's possible to walk to the left for $$$7$$$ seconds. Then Monocarp's character ends up in the point $$$-1$$$. Then he can leap to the right twice, the first leap ends in the point $$$4$$$, and the second leap ends in the point $$$9$$$. Two leaps take $$$12$$$ seconds. So, Monocarp reaches the goal in $$$7 + 12 = 19$$$ seconds.

In the second example, it's possible to start by leaping to the right. Then the character ends up in the point $$$15$$$, spending $$$10$$$ seconds. Then he has to walk to the right $$$5$$$ times, so he reaches the point $$$20$$$. The total time spent by Monocarp will be equal to $$$10 + 5 \cdot 5 = 35$$$ seconds.

In the third example, it's possible to leap to the right twice. Then the character ends up in the point $$$4$$$, spending $$$10$$$ seconds.