Optimal Fuel Load and Pit Stop Strategy

During an F1 race, when all other factors are equal, a car's speed is greatly affected by its fuel load. A car carrying too much fuel will be slower and consume fuel faster, while carrying too little fuel means more pit stops during the race. Therefore, it is crucial to determine the optimal initial fuel load and the pit stop fueling strategy in order to minimize the total race time.

You are given four integers:

• n: the total number of laps in the race.
• L: the base time (in seconds) to complete one lap.
• Q: the additional time penalty (in seconds) per unit of fuel carried at the start of a lap.
• P: the fixed time penalty (in seconds) incurred for each pit stop.

At the start of each stint (a sequence of consecutive laps without a pit stop) you can load the exact amount of fuel required for that stint. If you start a stint with s laps worth of fuel, then the lap times for that stint will be:

[ T_1 = L + Q \times s,\quad T_2 = L + Q \times (s-1),\quad \ldots,\quad T_s = L + Q \times 1. ]

The cost to run a stint of s laps is therefore:

[ C(s) = s \times L + Q \times \frac{s(s+1)}{2}. ]

Your task is to determine the optimal way to partition the n laps into one or more stints so that the total race time is minimized. Note that after every stint except the last one a pit stop is required (adding a penalty of P seconds).

Input Format: A single line containing four integers n L Q P separated by spaces.

Output Format: Output the minimal total race time as a number formatted with exactly two decimal places.

For example, consider the input 5 100 2 10:

• If no pit stop is taken, the total time is: \(5 \times 100 + 2 \times \frac{5 \times 6}{2} = 500 + 30 = 530\) seconds.
• A possible optimal strategy is to run a stint of 2 laps and then a stint of 3 laps. The time would be:
  • Stint 1: \(2 \times 100 + 2 \times \frac{2 \times 3}{2} = 200 + 6 = 206\) seconds,
  • Plus pit stop: 10 seconds,
  • Stint 2: \(3 \times 100 + 2 \times \frac{3 \times 4}{2} = 300 + 12 = 312\) seconds.

  Total = 206 + 10 + 312 = 528 seconds, which is optimal.

inputFormat

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

• n — the total number of laps.
• L — the base lap time.
• Q — the additional time per unit fuel at the beginning of a lap.
• P — the pit stop time penalty.

outputFormat

Output a single number — the minimal total race time, formatted with exactly two decimal places.

sample

5 100 2 10

528.00