Language: C++

#include <bits/stdc++.h>

using namespace std;

#define countof(a) (sizeof(a)/sizeof(*a))

#define vi vector<int>
#define vvi vector<vector<int> >
#define vpi vector<pi >
#define pi pair<int,int>
#define mp make_pair
#define fi first
#define se second
#define all(n) n.begin(), n.end()

#define FROMTO(var, from, to) for (register int var = (from), var##down = ((int)(to)) < ((int)(from));var##down ? (var >= (int)(to)) : (var <= (int)(to));var##down ? var-- : var++)
#define UPTO(var, from, to)   for (register int var = (from); var <= ((int)to); var++)
#define DOWNTO(var, from, to) for (register int var = (from); var >= ((int)to); var--)
#define FOR(var, to)          UPTO(var, 0, (to)-1)
#define DOWN(var, from)       DOWNTO(var, (from)-1, 0) 

#define INIT(var, val) FOR(i,countof(var)) var[i] = val
#define INPUT(var) FOR(i,countof(var)) cin >> var[i]
#define INPUT1(var) FOR(i,countof(var)) cin >> var[i], var[i]--

#define SORT(v) qsort(v,countof(v),sizeof(*v),int_less)
#define SORTT(v) qsort(v,countof(v),sizeof(*v),int_greater)
#define QSORT(v,b) qsort(v,countof(v),sizeof(*v),b)

#define MOD 1000000007
#define INF ((1 << 30)-1)
#define LINF ((1LL << 62)-1)

typedef uint8_t u8;
typedef uint16_t u16;
typedef uint32_t u32;
typedef uint64_t u64;
typedef int8_t s8;
typedef int16_t s16;
typedef int32_t s32;
typedef int64_t s64;

struct Comb {
    vector<vector<s64> > data;
    Comb(int n) { // O(n^2)
        data = vector<vector<s64> >(n+1,vector<s64>(n+1,1));
        UPTO(i,1,n) {
            FOR(j,i+1) {
                if (!j || j == i) data[i][j] = 1;
                else data[i][j] = data[i-1][j-1] + data[i-1][j];
            }
        }
    }
    
    s64 ncr(int n, int r) {
        return data[n][r];
    }
};

static inline int ri() {
  int a;
  scanf("%d", &a);
  return a;
}

int int_less(const void *a, const void *b) {
  return (*((const int*)a) - *((const int*)b));
}
int int_greater(const void *a, const void *b) {
  return (*((const int*)b) - *((const int*)a));
}


template<int mod>
struct ModInt{
    int x;
    ModInt():x(0){}
    ModInt(long long y):x(y>=0?y%mod:(mod-(-y)%mod)%mod){}
    ModInt &operator+=(const ModInt &p){
        if((x+=p.x)>=mod)x-=mod;
        return *this;
    }
    ModInt &operator-=(const ModInt &p){
        if((x+=mod-p.x)>=mod)x-=mod;
        return *this;
    }
    ModInt &operator*=(const ModInt &p){
        x=(int)(1LL*x*p.x%mod);
        return *this;
    }
    ModInt &operator/=(const ModInt &p){
        *this*=p.inverse();
        return *this;
    }
    ModInt operator-()const{return ModInt(-x);}
    ModInt operator+(const ModInt &p)const{return ModInt(*this)+=p;}
    ModInt operator-(const ModInt &p)const{return ModInt(*this)-=p;}
    ModInt operator*(const ModInt &p)const{return ModInt(*this)*=p;}
    ModInt operator/(const ModInt &p)const{return ModInt(*this)/=p;}
    bool operator==(const ModInt &p)const{return x==p.x;}
    bool operator!=(const ModInt &p)const{return x!=p.x;}
    explicit operator int() const { return x; }                           // added by QCFium
    ModInt operator=(const int p) {x = p; return ModInt(*this);} // added by QCFium
    ModInt inverse()const{
        int a=x,b=mod,u=1,v=0,t;
        while(b>0){
            t=a/b;
            a-=t*b;
            swap(a,b);
            u-=t*v;
            swap(u,v);
        }
        return ModInt(u);
    }
    friend ostream &operator<<(ostream &os,const ModInt<mod> &p){
        return os<<p.x;
    }
    friend istream &operator>>(istream &is,ModInt<mod> &a){
        long long x;
        is>>x;
        a=ModInt<mod>(x);
        return (is);
    }
};
typedef ModInt<MOD> mint;

mint mpow(s64 num, s64 times) { // O(log(times))
    mint next = num%MOD;
	mint res = 1;
	while (times) {
		if (times%2)
            res *= next;
		next *= next;
		times /= 2;
	}
	return res;
}

struct MComb {
    vector<mint> fact;
    vector<mint> inversed;
    MComb(int n) { // O(n+log(mod))
        fact = vector<mint>(n+1,1);
        UPTO(i,1,n) fact[i] = fact[i-1]*mint(i);
        inversed = vector<mint>(n+1);
        inversed[n] = mpow((int)fact[n], MOD-2);
        DOWN(i,n) inversed[i]=inversed[i+1]*mint(i+1);
    }
    
    mint ncr(int n, int r) {
        return (fact[n] * inversed[r] * inversed[n-r]);
    }
    
    mint npr(int n, int r) {
        return (fact[n] * inversed[n-r]);
    }
    
    mint nhr(int n, int r) {
        assert(n+r-1 < (int)fact.size());
        return ncr(n+r-1, r);
    }
};

int get(const vector<vector<int> >& a, int i, int j, int k, int l) {
	int n = a.size();
	int m = a[0].size();
	int res = a[k][l];
	if (i<=k && j<=l) {
		if (i) res -= a[i-1][l];
		if (j) res -= a[k][j-1];
		if (i&&j) res += a[i-1][j-1];
	} else if (i<=k) {
		if (i) res -= a[i-1][l];
		if (i) res -= a[i-1][m-1];
		res += a[k][m-1];
		if (j) res -= a[k][j-1];
		if (i&&j) res += a[i-1][j-1];
	} else if (j<=l) {
		if (j) res -= a[k][j-1];
		res += a[n-1][l];
		if (j) res -= a[n-1][j-1];
		if (i) res += a[i-1][l];
		if (i&&j) res -= a[i-1][j-1];
	} else {
		res -= a[k][l];
		res += a[n-1][m-1];
		if (j) res -= a[n-1][j-1];
		res += a[n-1][l];
		if (i) res -= a[i-1][m-1];
		res += a[k][m-1];
		if (i&&j) res += a[i-1][j-1];
		if (i) res -= a[i-1][l];
		if (j) res -= a[k][j-1];
		res += a[k][l];
	}
	return res;
}

int main() {
	int n = ri();
	int d = ri();
	int t[d][d];
	FOR(i,d) FOR(j,d) t[i][j] = 0;
	FOR(i,n) {
		int a = ri();
		t[a%d][ri()%d]++;
	}
	/*
	FOR(i,d) {
		FOR(j,d) cout << t[i][j] << " ";
		cout << endl;
	}*/
	
	int l = 0; int r = 1000000;
	while (r-l > 1) {
		int m = (l+r)/2;
		int tt[d][d];
		bool res = true;
		int lev0 = m/d;
		int lev1 = m/d*2+1;
		FOR(i,d) FOR(j,d) {
			tt[i][j] = max(0LL,t[i][j] - ((s64)m/d)*(m/d));
			if (tt[i][j] > lev1) res = false;
		}
		if (res) {
			res = false;
			int left = m%d;
			if (!left) {
				res = true;
				FOR(i,d) FOR(j,d) if (tt[i][j]) res = false;
			} else {
			int r00 = 0;
			FOR(i,d) FOR(j,d) if ((tt[i][j]&&tt[i][j]<=lev0)) r00++;
			vector<vector<int> > r0(d,vector<int>(d));
			r0[0][0] = (tt[0][0]&&tt[0][0]<=lev0);
			UPTO(i,1,d-1) r0[0][i] = r0[0][i-1] + (tt[0][i]&&tt[0][i]<=lev0);
			UPTO(i,1,d-1) {
				int cur = 0;
				FOR(j,d) {
					cur += (tt[i][j]&&tt[i][j]<=lev0);
					r0[i][j] = r0[i-1][j] + cur;
				}
			}
			
			int r11 = 0;
			FOR(i,d) FOR(j,d) if (tt[i][j]>lev0&&tt[i][j]<=lev1) r11++;
			vector<vector<int> > r1(d,vector<int>(d));
			r1[0][0] = (tt[0][0]>lev0&&tt[0][0]<=lev1);
			UPTO(i,1,d-1) r1[0][i] = r1[0][i-1] + (tt[0][i]>lev0&&tt[0][i]<=lev1);
			UPTO(i,1,d-1) {
				int cur = 0;
				FOR(j,d) {
					cur += (tt[i][j]>lev0&&tt[i][j]<=lev1);
					r1[i][j] = r1[i-1][j] + cur;
				}
			}
			
			// FOR(i,d) { FOR(j,d) cout << r1[i][j] << " "; cout << endl; }
			
			int r1r[d][d];
			FOR(i,d) FOR(j,d) r1r[i][j] = get(r1, i, j, (i+left-1)%d, (j+left-1)%d); // should be r11
			int r0r[d][d];
			FOR(i,d) FOR(j,d) r0r[i][j] = r00 - get(r0, (i+left-1)%d, (j+left-1)%d, (i-1+d)%d, (j-1+d)%d); // should be 0
			FOR(i,d) { FOR(j,d) if (!r0r[i][j] && r1r[i][j] == r11) { if (m == 4) { cout << i << j << endl; } res = true; break; } if (res) break; }
		}}
		if (res) r = m;
		else l = m;
	}
	cout << r-1 << endl;
	
    return 0;
}


Compiler output:
a.cc: In constructor 'Comb::Comb(int)':
a.cc:47:14: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   47 |         UPTO(i,1,n) {
      |              ^
a.cc:17:49: note: in definition of macro 'UPTO'
   17 | #define UPTO(var, from, to)   for (register int var = (from); var <= ((int)to); var++)
      |                                                 ^~~
a.cc:48:17: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   48 |             FOR(j,i+1) {
      |                 ^
a.cc:17:49: note: in definition of macro 'UPTO'
   17 | #define UPTO(var, from, to)   for (register int var = (from); var <= ((int)to); var++)
      |                                                 ^~~
a.cc:48:13: note: in expansion of macro 'FOR'
   48 |             FOR(j,i+1) {
      |             ^~~
a.cc: In constructor 'MComb::MComb(int)':
a.cc:144:14: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
  144 |         UPTO(i,1,n) fact[i] = fact[i-1]*mint(i);
      |              ^
a.cc:17:49: note: in definition of macro 'UPTO'
   17 | #define UPTO(var, from, to)   for (register int var = (from); var <= ((int)to); var++)
      |                                                 ^~~
a.cc:147:14: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
  147 |         DOWN(i,n) inversed[i]=inversed[i+1]*mint(i+1);
      |              ^
a.cc:18:49: note: in definition of macro 'DOWNTO'
   18 | #define DOWNTO(var, from, to) for (register int var = (from); var >= ((int)to); var--)
      |                                                 ^~~
a.cc:147:9: note: in expansion of macro 'DOWN'
  147 |         DOWN(i,n) inversed[i]=inversed[i+1]*mint(i+1);
      |         ^~~~
a.cc: In function 'int main()':
a.cc:203:13: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
  203 |         FOR(i,d) FOR(j,d) t[i][j] = 0;
      |             ^
a.cc:17:49: note: in definition of macro 'UPTO'
   17 | #define UPTO(var, from, to)   for (register int var = (from); var <= ((int)to); var++)
      |                                                 ^~~
a.cc:203:9: note: in expansion of macro 'FOR'
  203 |         FOR(i,d) FOR(j,d) t[i][j] = 0;
      |         ^~~
a.cc:203:22: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
  203 |         FOR(i,d) FOR(j,d) t[i][j] = 0;
      |                      ^
a.cc:17:49: note: in definition of macro 'UPTO'
   17 | #define UPTO(var, from, to)   for (register int var = (from); var <= ((int)to); var++)
      |                                                 ^~~
a.cc:203:18: note: in expansion of macro 'FOR'
  203 |         FOR(i,d) FOR(j,d) t[i][j] = 0;
      |                  ^~~
a.cc:204:13: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
  204 |         FOR(i,n) {
      |             ^
a.cc:17:49: note: in definition of macro 'UPTO'
   17 | #define UPTO(var, from, to)   for (register int var = (from); var <= ((int)to); var++)
      |                                                 ^~~
a.cc:204:9: note: in expansion of macro 'FOR'
  204 |         FOR(i,n) {
      |         ^~~
a.cc:221:21: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
  221 |                 FOR(i,d) FOR(j,d) {
      |                     ^
a.cc:17:49: note: in definition of macro 'UPTO'
   17 | #define UPTO(var, from, to)   for (register int var = (from); var <= ((int)to); var++)
      |                                                 ^~~
a.cc:221:17: note: in expansion of macro 'FOR'
  221 |                 FOR(i,d) FOR(j,d) {
      |                 ^~~
a.cc:221:30: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
  221 |                 FOR(i,d) FOR(j,d) {
      |                              ^
a.cc:17:49: note: in definition of macro 'UPTO'
   17 | #define UPTO(var, from, to)   for (register int var = (from); var <= ((int)to); var++)
      |                                                 ^~~
a.cc:221:26: note: in expansion of macro 'FOR'
  221 |                 FOR(i,d) FOR(j,d) {
      |                          ^~~
a.cc:222:39: error: no matching function for call to 'max(long long int, s64)'
  222 |                         tt[i][j] = max(0LL,t[i][j] - ((s64)m/d)*(m/d));
      |                                    ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/14/algorithm:60,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:51,
                 from a.cc:1:
/usr/include/c++/14/bits/stl_algobase.h:257:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  257 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/14/bits/stl_algobase.h:257:5: note:   template argument deduction/substitution failed:
a.cc:222:39: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 's64' {aka 'long int'})
  222 |                         tt[i][j] = max(0LL,t[i][j] - ((s64)m/d)*(m/d));
      |                                    ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algobase.h:303:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  303 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/14/bits/stl_algobase.h:303:5: note:   candidate expects 3 arguments, 2 provided
In file included from /usr/include/c++/14/algorithm:61:
/usr/include/c++/14/bits/stl_algo.h:5706:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(initializer_list<_Tp>)'
 5706 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/14/bits/stl_algo.h:5706:5: note:   candidate expects 1 argument, 2 provided
/usr/include/c++/14/bits/stl_algo.h:5716:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(initializer_list<_Tp>, _Compare)'
 5716 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/14/bits/stl_algo.h:5716:5: note:   template argument deduction/substitution failed:
a.cc:222:39: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
  222 |                         tt[i][j] = max(0LL,t[i][j] - ((s64)m/d)*(m/d));
      |                                    ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:230:37: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
  230 |                                 FOR(i,d) FOR(j,d) if (tt[i][j]) res = false;
      |                                     ^
a.cc:17:49: note: in definition of macro 'UPTO'
   17 | #define UPTO(var, from, to)   for (register int var = (from); var <= ((int)to); var++)
      |                                                 ^~~
a.cc:230:33: note: in expansion of macro 'FOR'
  230 |                                 FOR(i,d) FOR(j,d) if (tt[i][j]) res = false;
      |                                 ^~~
a.cc:230:46: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
  230 |                                 FOR(i,d) FOR(j,d) if (tt[i][j]) res = false;
      |                                              ^
a.cc:17:49: note: in definition of macro 'UPTO'
   17 | #define UPTO(var, from, to)   for (register int var = (from); var <= ((int)to); var++)
      |                                                 ^~~
a.cc:230:42: note: in expansion of macro 'FOR'
  230 |                                 FOR(i,d) FOR(j,d) if (tt[i][j]) res = false;
      |                                          ^~~
a.cc:233:29: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
  233 |                         FOR(i,d) FOR(j,d) if ((tt[i][j]&&tt[i][j]<=lev0)) r00++;
      |                             ^
a.cc:17:49: note: in definition of macro 'UPTO'
   17 | #define UPTO(var, from, to)   for (register int var = (from); var <= ((int)to); var++)
      |                                                 ^~~
a.cc:233:25: note: in expansion of macro 'FOR'
  233 |                         FOR(i,d) FOR(j,d) if ((tt[i][j]&&tt[i][j]<=lev0)) r00++;
      |                         ^~~
a.cc:233:38: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
  233 |                         FOR(i,d) FOR(j,d) if ((tt[i][j]&&tt[i][j]<=lev0)) r00++;
      |                                      ^
a.cc:17:49: note: in definition of macro 'UPTO'
   17 | #define UPTO(var, from, to)   for (register int var = (from); var <= ((int)to); var++)
      |                                                 ^~~
a.cc:233:34: note: in expansion of macro 'FOR'
  233 |                         FOR(i,d) FOR(j,d) if ((tt[i][j]&&tt[i][j]<=lev0)) r00++;
      |                                  ^~~
a.cc:236:30: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
  236 |                         UPTO(i,1,d-1) r0[0][i] = r0[0][i-1] + (tt[0][i]&&tt[0][i]<=lev0);
      |                              ^
a.cc:17:49: note: in definition of macro 'UPTO'
   17 | #define UPTO(var, from, to)   for (register int var = (from); var <= ((int)to); var++)
      |                                                 ^~~
a.cc:237:30: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
  237 |                         UPTO(i,1,d-1) {
      |                              ^
a.cc:17:49: note: in definition of macro 'UPTO'
   17 | #define UPTO(var, from, to)   for (register int var = (from); var <= ((int)to); var++)
      |                                                 ^~~
a.cc:239:37: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
  239 |                                 FOR(j,d) {
      |                                     ^
a.cc:17:49: note: in definition of macro 'UPTO'
   17 | #define UPTO(var, from, to)   for (register int var = (from); var <= ((int)to); var++)
      |                                                 ^~~
a.cc:239:33: note: in expansion of macro 'FOR'
  239 |                                 FOR(j,d) {