Description

Given an $N \times N$ square grid with the top-left corner as the start point ◎ at coordinates $(1, 1)$, where the $X$-axis increases to the right and the $Y$-axis increases downward, and each grid cell has side length $1$, as shown in the figure.

A car starts from ◎ and drives to the bottom-right corner ▲ at coordinates $(N, N)$.

Fuel depots are set at some grid intersections, where the car can refuel during the trip. The car must follow these rules:

1. The car can move only along grid edges, and with a full tank it can travel $K$ grid edges. The car starts with a full tank. There are no depots at the start or end points.
2. When the car traverses a grid edge, if its $X$-coordinate or $Y$-coordinate decreases, it must pay a fee of $B$; otherwise, there is no fee.
3. When the car encounters a depot during the trip, it must refuel to full and pay a refueling cost of $A$.
4. When needed, a new depot may be added at a grid point by paying an installation cost of $C$ (this does not include the refueling cost $A$).
5. $N, K, A, B, C$ are all positive integers and satisfy the constraints $2 \leq N \leq 100, 2 \leq K \leq 10$.

Design an algorithm to compute the minimum total cost for the car to travel from the start to the destination.

Input Format

The first line contains the values of $N, K, A, B, C$.

Starting from the second line, an $N \times N$ binary matrix is given, ending at line $N + 1$, with $N$ values per row.

If the value at row $i$, column $j$ is $1$, it means a fuel depot is set at the grid intersection $(i, j)$; if it is $0$, no depot is set there. Adjacent numbers in the same row are separated by spaces.

Output Format

Output the minimum total cost at the end of the program.

9 3 2 3 6
0 0 0 0 1 0 0 0 0
0 0 0 1 0 1 1 0 0
1 0 1 0 0 0 0 1 0
0 0 0 0 0 1 0 0 1
1 0 0 1 0 0 1 0 0
0 1 0 0 0 0 0 1 0
0 0 0 0 1 0 0 0 1
1 0 0 1 0 0 0 1 0
0 1 0 0 0 0 0 0 0

12

Hint

Constraints: $2 \leq N \leq 100, 2 \leq K \leq 10$.

Translated by ChatGPT 5