#include <bits/stdc++.h>
#define int long long
using namespace std;
int dp[1000][1000];
void add(deque<int> &d, int value){
    while (d.size() && value > d.back()){
        d.pop_back();
    }
    d.push_back(value);
}
void dlt(deque<int> &d, int value){
    if (d.front() == value) d.pop_front();
}
bool checker(int num, int others, int k){
    bool row[k], zap[k];
    for (int i=0; i < k; i++) row[i] = false;
    for (int i=0; i < k; i++) for (int j=0; j < k; j++) if (dp[i][j] > (num-1)*num) row[i] = true;
    vector<deque<int> > v(k);
    for (int i=0; i < k; i++) for (int j=0; j < others; j++){
        add(v[i], dp[i][j]);
    }
    //exit(0);
    int now = 0;
    for (int i=0; i < k;i++){
        //cout << i << " ";
        for (int j=0; j < k; j++) zap[j] = row[j];
        int mmx = 0;
        for (int j=0; j < k; j++) if (v[j].front() > (num-1)*(num-1)) zap[j] = true;
        for (int j=0; j < k; j++) mmx = max(mmx, v[j].front());
        bool abl = (mmx <= num*(num-1));
        int tet = 0;
        int sum = 0;
        for (int p=0;p<others;p++) sum+=zap[p];
        for (int p=0;p<k;p++){
            if (sum==0 && abl) return true;
            sum -= zap[tet%k];
            sum += zap[(tet+others)%k];
            tet++;
        }
        for (int j=0;j<k;j++){
            dlt(v[j], dp[j][now%k]);
            add(v[j], dp[j][(now+others)%k]);
        }
        now++;
    }
    return false;
}
signed main(){
    int n, k;
    cin >> n >> k;
    for (int i=0; i < n; i++){
        int x, y;
        cin >> x >> y;
        dp[x%k][y%k]++;
    }
    int mx = 0;
    for (int i=0;i<k;i++) for (int j=0;j<k;j++) mx = max(mx, dp[i][j]);
    int num = 1;
    while (num*num < mx) num++;
    int L = 0, R = k;
    while (R-L>1){
        int M = (L+R)/2;
        if (checker(num, M, k)) L = M;
        else R = M;
        //return 0;
    }
    cout << num*k-L-1 << endl;

}
