module mod_square_rotation
  implicit none
  integer :: d, s(3,0:2000,0:2000) = 0
contains
  subroutine cumsum(a,k)
    integer, intent(in) :: a(:,:), k
    integer :: i, j, l, b(3,d,d)
    b(3,d,d) = 0
    do i = 1, d
      do j = 1, d
        if (a(i,j) > (k+1)*(k+1)) b(1,i,j) = b(1,i,j)+1
        if (a(i,j) > k*k) b(2,i,j) = b(2,i,j)+1
        if (a(i,j) > k*(k+1)) b(3,i,j) = b(3,i,j)+1
      end do
    end do
    do i = 1, 2*d
      do j = 1, 2*d
        s(:,i,j) = s(:,i-1,j)+s(:,i,j-1)-s(:,i-1,j-1) &
        & +b(:,mod(i-1,d)+1,mod(j-1,d)+1)
      end do
    end do
  end
  integer function getsum(l,i1,j1,i2,j2)
    integer, intent(in) :: l, i1, j1, i2, j2
    getsum = s(l,i1,j1)-s(l,i2-1,j1)-s(l,i1,j2-1)+s(l,i2-1,j2-1)
  end
  logical function check(b)
    integer, intent(in) :: b
    integer :: i, j
    check = .false.
    do i = 1, d
      do j = 1, d
        if (getsum(1,i,j,i+b,j+b) == 0) cycle
        if (getsum(2,i+b+1,j+b+1,i+d-1,j+d-1) == 0) cycle
        if (getsum(3,i+b+1,j,i+d-1,j+b) == 0) cycle
        if (getsum(3,i,j+b+1,i+b,j+d-1) == 0) cycle
        check = .true.
        return
      end do
    end do
  end
end module mod_square_rotation
program square_rotation
  use mod_square_rotation
  implicit none
  integer :: n, x, y, a(0:1000,0:1000) = 0, i, j, m, k, l, r
  logical :: ok
  read(*,*) n, d
  do i = 1, n
    read(*,*) x, y
    x = mod(x,d)
    y = mod(y,d)
    a(x,y) = a(x,y)+1
  end do
  m = maxval(a(0:d-1,0:d-1))
  k = 0
  do
    if (m <= (k+1)*(k+1)) exit
    k = k+1
  end do
  call cumsum(a(0:d-1,0:d-1),k)
  l = -1
  r = d-1
  do while (r-l > 1)
    m = (l+r)/2
    if (check(m)) then
      r = m
    else
      l = m
    end if
  end do
  write(*,'(i0)') k*d+r
end program square_rotation