Choose the cheapest way to buy train tickets for a given number of trips.
Cheap Travel
You need to make exactly trips. There are two ticket types:
- a single-trip ticket that costs
- a pass that covers up to trips and costs
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.
Input Format
The input consists of three integers:
- — number of trips
- — trips covered by one pass
- — price of one single-trip ticket
- — price of one pass
Output Format
Print one integer: the minimum total cost to make all trips.
Constraints
- are positive integers
- A pass may be used for up to trips
- It is always allowed to buy only single-trip tickets
- The answer fits in a 64-bit signed integer
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
Unlock deeper context for this problem
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.