Choose the cheapest way to buy train tickets for a given number of trips.
You need to make exactly trips. There are two ticket types:
You may buy any number of each ticket type. Your goal is to pay the minimum possible total cost to cover all trips.
Return the minimum total price needed.
The input consists of three integers:
Print one integer: the minimum total cost to make all trips.
Example 1
Input
10 3 5 12
Output
40
Explanation
Three full passes would cost 36 and cover 9 trips, plus one single ticket for the last trip costs 5. Total: 41. But buying ten single tickets costs 50, so the best option is 3 passes and 1 single ticket = 41.
Example 2
Input
7 4 2 15
Output
14
Explanation
A pass is more expensive than 4 single tickets, so the cheapest choice is to buy 7 single tickets: 7 × 2 = 14.
Premium problem context
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.