One possible upper bound is \(|S _ x-T _ x|+|S _ y-T _ y|\). (A toll not greater than this can be achieved by moving horizontally by \(|S _ x-T _ x|\), and then vertically by \(|S _ y-T _ y|\).)

If \(K=1\), it immediately follows that this is equal to the answer.

Now, we assume \(K\geq2\).

If the answer is strictly less than this upper bound, then optimal paths pass through a large tile. (If it only passes through small tiles, the toll coincides with the upper bound.)

We enumerate all possible large tiles passing through for the first time in an optimal tour, and those for the last time.

The possible candidates of the first large tiles are:

• if \((S _ x+0.5,S _ y+0.5)\) is on a large tile, then that large tile;
• otherwise, for each of the four direction, the first large tile you pass through when moving in that direction, for a total of four large tiles.

One can immediately calculate tolls from the tile containing \((S _ x+0.5,S _ y+0.5)\) to each large tile. (Note that only small tiles will be used until reach the large tile by assumption. The value calculated here does not have to be the minimum toll required to reach the large tile.)

Likewise, the last large tile is also limited to four candidates, and the toll required to reach from each large tile to \((T _ x+0.5,T _ y+0.5)\) as well.

For these at most \(16\) pairs, it is sufficient to find the minimum toll required to travel between large tiles.

One can apply pruning to reduce pairs, but it is fast enough without pruning.

We consider how to find the minimum toll required to travel between two tiles.

First, one can travel between two large tiles sharing a vertex for a toll of \(2\).
Also, one can travel between a large tile \([i,i+K]\times[j,j+K]\) and another \([i+K,i+2K]\times[j,j+K]\) for a toll of \(K=2\), which must be taken into account only for \(K=2\). (Same applies to vertical moves.)

Therefore, the minimum toll required to travel from a large tile \(|a-c|+|b-d|+\left\vert\dfrac{|a-c|-|b-d|}2\right\vert\) to another \([cK,(c+1)K]\times[dK,(d+1)K]\) can be written as follows:

• \(|a-c|+|b-d|+\left\vert\dfrac{|a-c|-|b-d|}2\right\vert\) if \(K=2\);
• \(|a-c|+|b-d|+\bigl\vert|a-c|-|b-d|\bigr\vert=|a+b-c-d|+|a-b-c+d|\) if \(K\neq2\).

The problem can be solved by using this feature.

The following is sample code.

#include <iostream>
#include <vector>
#include <tuple>

int main() {
    using namespace std;
    
    unsigned long K;
    cin >> K;
    unsigned long Sx, Sy, Tx, Ty;
    cin >> Sx >> Sy >> Tx >> Ty;
    // Shift everything by K
    Sx += K;
    Sy += K;
    Tx += K;
    Ty += K;
    
    // Put the upper bound
    unsigned long dist{max(Tx, Sx) - min(Tx, Sx) + max(Ty, Sy) - min(Ty, Sy)};
    
    // If 1 < K, consider tours via a large tile
    if(1 < K){
        vector<tuple<unsigned long, unsigned long, unsigned long>> large_start; // Candidates of large tiles visiting for the first time
        if(((Sx / K) ^ (Sy / K)) & 1) // If the starting point is in a large tile,
            large_start.emplace_back(Sx / K, Sy / K, 0); // the candidate is that large tile
        else{ // Otherwise, the candidates are the nearest tile in one of the four directions
            large_start.emplace_back(Sx / K - 1, Sy / K, 1 + Sx % K); // left
            large_start.emplace_back(Sx / K + 1, Sy / K, K - Sx % K); // right
            large_start.emplace_back(Sx / K, Sy / K - 1, 1 + Sy % K); // down
            large_start.emplace_back(Sx / K, Sy / K + 1, K - Sy % K); // up
        }

        vector<tuple<unsigned long, unsigned long, unsigned long>> large_goal; // Candidates of large tiles visiting for the last time
        if(((Tx / K) ^ (Ty / K)) & 1) // If the ending point is in a large tile
            large_goal.emplace_back(Tx / K, Ty / K, 0); // the candidate is that large tile
        else{ // Otherwise, the candidates are the nearest tile in one of the four directions
            large_goal.emplace_back(Tx / K - 1, Ty / K, 1 + Tx % K); // left
            large_goal.emplace_back(Tx / K + 1, Ty / K, K - Tx % K); // right
            large_goal.emplace_back(Tx / K, Ty / K - 1, 1 + Ty % K); // down
            large_goal.emplace_back(Tx / K, Ty / K + 1, K - Ty % K); // up
        }

        // Check if K = 2
        if(K == 2)
            for(const auto& [x, y, d1] : large_start)
                for(const auto& [z, w, d2] : large_goal){
                    const auto x_diff{max(x, z) - min(x, z)};
                    const auto y_diff{max(y, w) - min(y, w)};
                    dist = min(dist, d1 + d2 + x_diff + y_diff + (max(x_diff, y_diff) - min(x_diff, y_diff)) / 2);
                }
        else
            for(const auto& [x, y, d1] : large_start)
                for(const auto& [z, w, d2] : large_goal)
                    dist = min(dist, d1 + d2 + max(x + y, z + w) - min(x + y, z + w) + max(x + w, z + y) - min(x + w, z + y));
    }
    cout << dist << endl;
    return 0;
}