Let \((i_S, j_S)\) and \((i_T, j_T)\) be the positions of the two stations. Without loss of generality we assume that \(i_S \leq i_T\).
Here, we will explain how to find the choice of two places of building stations with the minimum cost of the construction subject to \(j_S \leq j_T\). That is, we only consider the cases where \((i_T, j_T)\) is in the south east of \((i_S, j_S)\). This is because we can check the pairs of stations \(j_S > j_T\) by applying the procedures mentioned below again after flipping entire grid horizontally.

In order to find the way of building two stations such that \(i_S \leq i_T\) and \(j_S \leq j_T\) so that the construction expense is minimum, we first rephrase the process of building the railway as follows.

1. First, Aoki alights on an arbitrary square and construct a station there. Here, he has to pay the cost of building a station.

2. Aoki repeats one or more times the following action: “move from the square he currently stands to an adjacent square in the south or east, while building a railway.” He cannot go outside the grid. Every time he makes a move, he has to pay \(C\) yen of building railway.

3. Build a station in the square Aoki finishes the moves, and Aoki flies away somewhere. Here, he has to pay the cost of building a station.

Among all the ways of building railway, finding the one with the minimum cost of construction is our objectives.
We solve this problem with DP (Dynamic Programming). First, we define \(\mathrm{dp}[i][j]\) as

\(\mathrm{dp}[i][j]\) := (The minimum total cost paid so far when Aoki has already built one station and is currently in \((i, j)\)).

The situation where “Aoki has already built one of the station and is currently at \((i, j)\)” can be divided into the following three cases:

• Aoki has landed to \((i, j)\) and built a station there.
• Aoki has come from \((i-1, j)\) to here \((i, j)\) while building railroad.
• Aoki has come from \((i, j-1)\) to here \((i, j)\) while building railroad.

Corresponding to the three cases above, \(\mathrm{dp}[i][j]\) can be represented by the following recurrence relations:

\(\mathrm{dp}[i][j] = \min \lbrace A_{i, j}, \mathrm{dp}[i-1][j] + C, \mathrm{dp}[i][j-1] + C \rbrace\).

Here, for \(i = 0\) or \(j = 0\) we define \(\mathrm{dp}[i][j] := \infty\).
With this recurrence relations, we can find \(\mathrm{dp}[i][j]\) for every \(i = 1, 2, \ldots, H, j = 1, 2, \ldots, W\) in a total of \(\mathrm{O}(HW)\) time.

Now we describe how to find the answer for the original problem using the resulting values of \(\mathrm{dp}[i][j]\). First, let us define \(X[i][j]\) by

\(X[i][j]\) := ( The minimum possible total costs for Aoki to build the second station at \((i, j)\) and fly away somewhere).

The situation where “the second station was built at \((i, j)\) and Aoki flew away somewhere” can be split into the following two cases (Note that the two stations have to be built in different squares):

• Aoki has come from \((i-1, j)\) to here \((i, j)\) while building railroad, built a station at \((i, j)\) and flew away.
• Aoki has come from \((i, j-1)\) to here \((i, j)\) while building railroad, built a station at \((i, j)\) and flew away.

Corresponding to the two cases above, we can find \(X[i][j]\) by the following formula:

\(X[i][j] = \min \lbrace \mathrm{dp}[i-1][j] + C + A_{i, j}, \mathrm{dp}[i][j-1] + C + A_{i, j} \rbrace\)

Since Aoki will fly away from some square, it is sufficient to check \(X[i][j]\) for every \(i = 1, 2, \ldots, H, j = 1, 2, \ldots, W\).
Therefore, the answer for this problem is \(\displaystyle\min_{1 \leq i \leq W, 1 \leq j \leq H} X[i][j]\).

The time complexity for this algorithm is \(\mathrm{O}(HW)\), which is fast enough to get accepted for this problem.