Minimum Fuel Required to Reach Destination

You are given a ship that needs to travel from a starting port to a destination port covering a total distance of \(D\). The ship has a maximum fuel tank capacity \(C\) which limits the distance it can travel without refueling. In between, there are several fuel depots located along the route. The distances of these depots from the starting port are provided in increasing order. Your task is to determine the minimum total amount of fuel required to reach the destination. If at any point the distance to the next depot (or to the destination) exceeds the tank capacity \(C\), it is impossible to complete the journey and you should output \(-1\).

Input Constraints:

• \(0 \leq N\) where \(N\) is the number of depots.
• \(D, C\) are positive integers.
• The depot distances are given in sorted order and each is between \(0\) and \(D\).

Note: Even if the total fuel used along the segments is less than \(C\), the answer should be \(\max(\text{fuel_used}, C)\).

inputFormat

The input is read from stdin and consists of:

• One line with three integers: num_depots total_distance tank_capacity.
• If num_depots > 0, a second line with num_depots integers representing the distances of the depots from the starting port.

If there are no depots, the second line is omitted.

outputFormat

Output a single integer to stdout, which is the minimum total fuel required to reach the destination. If the destination cannot be reached due to a gap exceeding the tank capacity, output \(-1\).

2 1000 500
300 600

1000