Minimum Cost Car Journey with Fuel Stops

Given an \(N\times N\) square grid with each cell having side length \(1\) and the top-left corner at \((1,1)\) marked with \(\bigcirc\) (the start), and the bottom-right corner \((N,N)\) marked with \(\triangle\) (the destination), a car must travel from the start to the destination along the grid edges.

The car starts with a full tank of fuel and can travel exactly \(K\) grid edges per full tank. Note that fuel capacity is measured in the number of edges. There is no fuel station at the start or destination. However, there are a number of fuel depots set up at some grid intersections. When the car passes through an intersection with a fuel depot, it is forced to refill its tank to full capacity and must pay a refueling fee \(A\).

If needed, you are allowed to construct a new fuel depot at any grid intersection (except at the start and destination). Constructing a depot costs \(C\) (this cost does not include the later refueling fee \(A\) when the car visits it).

The car’s movement also has an associated cost: every time it traverses a grid edge, if the new \(X\) coordinate or the new \(Y\) coordinate is less than the previous coordinate (i.e. the car moves left or upward), a penalty cost of \(B\) is incurred; moving right or downward is free.

The goal is to plan a route from \((1,1)\) to \((N,N)\) that minimizes the total cost. The total cost is the sum of the refueling costs (\(A\) each time the car refuels at a depot), the depot construction costs (\(C\) for each newly constructed depot), and any penalty costs \(B\) incurred if the car ever moves left or upward.

Observations:

• The car begins fully fueled, so its first leg from the start does not require a depot, and the destination does not have or need a fuel depot.
• Since the destination is at \((N,N)\) and the start at \((1,1)\), a monotonic (only right and down moves) path has no penalty cost. Hence, if we can partition the monotonic Manhattan path into segments of at most \(K\) moves, no penalty cost \(B\) will ever be incurred.
• The Manhattan distance from \((1,1)\) to \((N,N)\) is \(2N-2\). If \(2N-2 \le K\) then the car can reach the destination without any refueling stops and the cost is \(0\).
• If \(2N-2 > K\), then the journey must be broken into legs such that each leg has at most \(K\) moves. Let the number of legs be \(L=\lceil \frac{2N-2}{K} \rceil\). In this case the car must stop for refueling in \(L-1\) intermediate legs. For each stop, a depot must be present. Since there are no depots at the start and destination, each intermediate depot will have to be constructed, incurring cost \(C\) plus the refueling cost \(A\).

Thus, the minimum total cost is given by:

[ \text{cost} = \begin{cases} 0, & \text{if } 2N-2 \le K,\ \left(\lceil \frac{2N-2}{K} \rceil - 1\right) \times (A+C), & \text{otherwise.} \end{cases} ]

Design an algorithm that computes the minimum cost for the car to travel from the start to the destination following the above rules and constraints.

inputFormat

The input consists of a single line containing five positive integers: \(N\) (the grid size), \(K\) (the number of grid edges the car can traverse on a full tank), \(A\) (the refueling cost at a depot), \(B\) (the penalty cost when moving left or up), and \(C\) (the construction cost to build a depot). It is guaranteed that \(2 \le N \le 100\) and \(2 \le K \le 10\).

outputFormat

Output a single integer, the minimum total cost required for the car to travel from \((1,1)\) to \((N,N)\) under the given rules.

sample

5 4 10 5 3

13