9052. Shot at a target

Agent Johnny English decided to practice shooting. To do this, he decided to do exactly n shots. His pistol has a magazine with m cartridges, which, of course, is not initially loaded.

Johnny English can fully reload his pistol in a seconds or add one cartridge to the chamber in b seconds. One shot takes exactly one second. Help him to find the minimum amount of time Agent Johnny English can make exactly n shots. Of course, he cannot fire an empty pistol and cannot put a new cartridge into an already full magazine.

Input. The first line contains four integers n, m, a and b (1 ≤ n, m, a, b ≤ 10⁴) – the number of shots to be fired, the size of the pistol magazine, the time it takes to fully reload the magazine and the time to load one cartridge.

Output. Print one number – the minimum time it will take for the agent to fire exactly n shots.

Sample input	Sample output
3 2 1 1	5

SOLUTION

mathematics

Algorithm analysis

The pistol chamber holds m cartridges. You can put one cartridge to the chamber in b seconds. If m * b < a, then set a = m * b. Now a contains the minimum time to reload the entire pistol.

To make n shots with a chamber size of m rounds, you must:

· Fully reload the magazine n / m times, which can be done in (n / m) * a seconds;

· To fire the remaining n % m shots, you can either reload the magazine once in a seconds or put cartridges in the magazine in (n % m) * b seconds. We perform operation that requires less time. It will take min(a, (n % m) * b) seconds.

· you can make n shots in n seconds;

The total time of training is

(n / m) * a + min(a, (n % m) * b) + n

seconds.

Example

The input sample contains the following data: n = 3, m = 2, a = 1, b = 1.

The minimum time to reload the entire pistol is

a = min(a, m * b) = min(1, 2 * 1) = 1

The minimum time to make n shots is

(n / m) * a + min(a, (n % m) * b) + n =

(3 / 2) * 1 + min(1, (3 % 2) * 1) + 3 =

1 + 1 + 3 = 5

Algorithm realization

Read the input data.

scanf("%lld %lld %lld %lld", &n, &m, &a, &b);

Find the minimum time a for a reload of entire pistol.

a = min(a, m * b);

Find the minimum time for making n shots.

res = (n / m) * a + min(a, (n % m) * b) + n;

Print the answer.

printf("%lld\n", res);