Since there is a constraint that a gas station cannot be used both outbound and return trip, it is a good idea to consider at once for each gas station how to behave during the outbound and return trip, instead of independently considering the outbound trip end the return trip.

Let \(dp_{i,j,k}\) (DP stands for dynamic programming) be the minimum amount of money required to pay for the gas stations at the \(X_1, X_2, \ldots, X_i\) if he has \(j\) liters of gas in the outbound trip and \(k\) liters in the return trip at coordinate \(X_i\). Here, if he uses the gas station at coordinate \(X_i\), we define \(j\) as the amount of the gas after fueling, and \(k\) as that before fueling.

Note that the answer to this problem is the minimum \(dp_{N,j,j}\) for \(j = 0,1, \ldots, H\).

If we know the amount of fuel at coordinate \(X_i\), the amount at coordinate \(X_{i+1}\) can be easily found.
Specifically, take into account the following four cases.

• When he has \(j\) liters of fuel at coordinate \(X_i\) in the outbound trip, the amount at coordinate \(X_{i+1}\) becomes \(j - (X_{i+1} - X_i)\) if \(j \geq X_{i+1} - X_i\), and he is unreachable to \(X_{i+1}\) otherwise.

• When he has \(k\) liters of fuel at coordinate \(X_i\) in the return trip, the amount at coordinate \(X_{i+1}\) is \(k + X_{i+1} - X_i\) if \(k + X_{i+1} - X_i \leq H\), and otherwise, it turns out that it is impossible that he has \(k\) liters of fuel at coordinate \(X_i\).

• If he has \(j\) liters of fuel before using the gas station at coordinate \(X_i\) in the outbound trip, the amount becomes \(\min(j+F_i,H)\) by using the gas station.

• If he has \(k\) liters of fuel after using the gas station at coordinate \(X_i\) in the return trip, the possible amount of fuel before using the gas station is between \(k - F_i\) and \(k\) liters if \(k = H\), and just \(k - F_i\) liters if \(F_i \leq k < H\).

By performing the DP according to the facts above, the answer can be obtained in a total of \(O(N^3)\) time.