Minimum Effort to Divide Bricks

Aya is working on a construction site and has n bricks that must be divided equally into two groups to be delivered to two different endpoints. Note that bricks cannot be cut into pieces.

She has two ways to move a brick:

• Carry a brick by hand, which costs a units of effort per brick.
• Use a trolley that can hold up to k bricks (the trolley can be partially loaded) which costs b units of effort each time it is used.

Aya can mix these methods arbitrarily. For each group (each containing \( x = \frac{n}{2} \) bricks), she needs to decide on an optimal combination of trolley trips and individual brick carries in order to minimize the effort. In one group, if she uses \( t \) trolley trips then she can move at most \( t\times k \) bricks with the trolley. If \( t\times k \) is less than \( x \), she will need to move the remaining \( x - t\times k \) bricks one by one. However, even if \( t\times k \) exceeds \( x \) (since the trolley may not be full), the cost of that trolley trip is still incurred.

The cost to deliver one half is therefore:

[ C(x) = \min_{0 \le t \le T} \begin{cases} t\times b + (x - t\times k)\times a & \text{if } t\times k < x,\ t\times b & \text{if } t\times k \ge x, \end{cases} ]

where \( T = \lceil \frac{x}{k} \rceil \). The total minimum effort is then:

[ \text{Total Cost} = 2\times C(x). ]

You are given four integers n, a, b and k in one line, where n is guaranteed to be even.

inputFormat

The input consists of a single line containing four space-separated integers:

• n: the total number of bricks (an even integer).
• a: the effort cost to carry one brick individually.
• b: the effort cost to use the trolley once.
• k: the maximum number of bricks the trolley can carry.

outputFormat

Output a single integer representing the minimum total effort required to deliver all bricks equally to the two endpoints.

sample

10 2 15 3

20