答えの上界として、\(|S _ x-T _ x|+|S _ y-T _ y|\) が考えられます（左右方向に \(|S _ x-T _ x|\) だけ移動し、その後上下方向に \(|S _ y-T _ y|\) だけ移動することで、この上界以下の値を達成できます）。

\(K=1\) のとき、これが答えと等しいことがすぐにわかります。

以下、\(K\geq2\) とします。

答えがこの上界より真に小さいとき、答えを実現する移動方法では大タイルを通ることがわかります（小タイルしか通らない場合、支払う通行料が上界と一致します）。

答えを実現する移動方法においてはじめに到達する大タイルと最後に到達する大タイルの組を全探索することを考えます。

はじめに到達する大タイルとしてありえるものは、

• \((S _ x+0.5,S _ y+0.5)\) が大タイルの上にあるなら、その大タイル
• そうでなければ、上下左右のそれぞれについて、その方向にのみ移動したときに最初に到達する \(4\) つの大タイル

に限られます。 \((S _ x+0.5,S _ y+0.5)\) を含むタイルからそれぞれの大タイルへ移動するのにかかる通行料はすぐに計算できます（仮定より、それぞれの大タイルへ到達するまでに使うのは小タイルのみであるとしてよいことに注意してください。ここで計算された値がそれぞれの大タイルへ移動するのにかかる通行料の最小値でなくとも答えには影響ありません）。

同様に、最後に到達する大タイルとしてありえるものもたかだか \(4\) つに限られ、それぞれの大タイルから \((T _ x+0.5,T _ y+0.5)\) を含むタイルへ移動するのにかかる通行料も求めることができます。

そして、これらの組たかだか \(16\) 通りに対して、それぞれの大タイル間を移動するのにかかる通行料の最小値を求められればよいです。

枝刈りをすることで調べる組の個数を減らすことができる場合もありますが、しなくても十分高速です。

\(2\) つの大タイル間を移動するのにかかる通行料の最小値を求めることを考えます。

まず、一点を共有する \(2\) つの大タイルは、\(2\) の通行料を支払うことで行き来することができます。
また、\([i,i+K]\times[j,j+K]\) の大タイルと \([i+K,i+2K]\times[j,j+K]\) の大タイルを \(K+1\) の通行料を支払うことで行き来することができ、\(K=2\) のときに限り考慮に入れる必要があります（上下方向も同様です）。

以上より、\([aK,(a+1)K]\times[bK,(b+1)K]\) の大タイルから \([cK,(c+1)K]\times[dK,(d+1)K]\) の大タイルへ移動するのにかかる通行料の最小値は以下のように書けます。

• \(K=2\) のとき、\(|a-c|+|b-d|+\left\vert\dfrac{|a-c|-|b-d|}2\right\vert\)
• \(K\neq2\) のとき、\(|a-c|+|b-d|+\bigl\vert|a-c|-|b-d|\bigr\vert=|a+b-c-d|+|a-b-c+d|\)

これを用いることでこの問題を解くことができます。

実装例は以下のようになります。

#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;
    // K ずつ右上にずらしておく
    Sx += K;
    Sy += K;
    Tx += K;
    Ty += K;
    
    // 上界を入れておく
    unsigned long dist{max(Tx, Sx) - min(Tx, Sx) + max(Ty, Sy) - min(Ty, Sy)};
    
    // 1 < K のとき、大タイルを経由する移動を考える
    if(1 < K){
        vector<tuple<unsigned long, unsigned long, unsigned long>> large_start; // はじめに到達する大タイルの候補
        if(((Sx / K) ^ (Sy / K)) & 1) // 開始位置が大タイルなら
            large_start.emplace_back(Sx / K, Sy / K, 0); // その大タイル
        else{ // そうでなければ、四方向いずれかで最も近い大タイルが候補
            large_start.emplace_back(Sx / K - 1, Sy / K, 1 + Sx % K); // 左
            large_start.emplace_back(Sx / K + 1, Sy / K, K - Sx % K); // 右
            large_start.emplace_back(Sx / K, Sy / K - 1, 1 + Sy % K); // 下
            large_start.emplace_back(Sx / K, Sy / K + 1, K - Sy % K); // 上
        }

        vector<tuple<unsigned long, unsigned long, unsigned long>> large_goal; // 最後に到達する大タイルの候補
        if(((Tx / K) ^ (Ty / K)) & 1) // 終了位置が大タイルなら
            large_goal.emplace_back(Tx / K, Ty / K, 0); // その大タイル
        else{ // そうでなければ、四方向いずれかで最も近い大タイルが候補
            large_goal.emplace_back(Tx / K - 1, Ty / K, 1 + Tx % K); // 左
            large_goal.emplace_back(Tx / K + 1, Ty / K, K - Tx % K); // 右
            large_goal.emplace_back(Tx / K, Ty / K - 1, 1 + Ty % K); // 下
            large_goal.emplace_back(Tx / K, Ty / K + 1, K - Ty % K); // 上
        }

        // 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;
}