Robot Cooking Scheduling

Little \(X\) is commanding \(M\) robots to cook a simple dish: boiled vegetables. In order to prepare one vegetable, two steps are required: cleaning and boiling. Note that the same vegetable cannot be cleaned and boiled simultaneously, nor can it be boiled before being cleaned.

The procedure is as follows: whenever a robot becomes idle, it is assigned a new task according to these rules:

• If there is at least one vegetable that has not been cleaned yet, the robot will clean one of them.
• Otherwise, if there is at least one vegetable that has been cleaned but not yet boiled, the robot will boil one of them.
• If neither task remains, the robot shuts down.

There are \(N\) vegetables in total. Every cleaning operation takes \(A\) minutes and every boiling operation takes \(B\) minutes. Under the above command policy, determine the total number of minutes needed to finish cooking all the vegetables. All robots work concurrently. Note that when multiple robots become idle at the same time, they are processed one by one: the robot processed earlier will pick its task first. (This may cause some robots to start boiling earlier than others.)

Input/Output Explanation: The robots follow the fixed rule above regardless of global optimization; your program should simulate this process exactly.

Note: All formulas are formatted in \(\LaTeX\). For example, the cleaning time is given by \(A\) and the boiling time by \(B\). Other parameters are \(N\) and \(M\).

inputFormat

The input consists of a single line containing four space‐separated integers: \(N\), \(M\), \(A\) and \(B\). Here, \(N\) is the number of vegetables, \(M\) is the number of robots, \(A\) is the number of minutes needed to clean a vegetable, and \(B\) is the number of minutes to boil a vegetable.

outputFormat

Output a single integer representing the total number of minutes required to finish cooking all \(N\) vegetables under the given policy.

sample

3 2 1 3

7