program square_rotation
  implicit none
  integer :: n, d, x, y, a(0:1000,0:1000) = 0, k, i, j, l, r, m, b
  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
  l = -1
  r = d
  do while (r-l > 1)
    m = (l+r)/2
    ok = .true.
    do i = 0, d-1
      do j = 0, d-1
        if (i <= m .and. j <= m) then
          b = (k+1)*(k+1)
        else if (i > m .and. j > m) then
          b = k*k
        else
          b = k*(k+1)
        end if
        if (a(i,j) > b) then
          ok = .false.
          goto 100
        end if
      end do
    end do
100 if (ok) then
      r = m
    else
      l = m
    end if
  end do
  write(*,'(i0)') k*d+r
end program square_rotation