{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE TupleSections #-}
import qualified Data.ByteString.Lazy.Char8 as B
import Data.Maybe
-- import Data.List
import qualified Data.Vector.Unboxed as VU
import qualified Data.Vector.Unboxed.Mutable as VUM
import Control.Monad
-- import Control.Monad.ST
-- import Debug.Trace

solve :: Int -> Int -> [(Int,Int)] -> Int
solve n d xys = ans
  where

  enc x y = (y * d) + x

  vec :: VU.Vector Int
  vec = VU.create $ do
    v <- VUM.replicate (d*d) 0
    forM_ xys $ \(x,y) -> do
      VUM.modify v (+ 1) (enc (x `mod` d) (y `mod` d))
    return v

  dMax = VU.maximum vec

  horiz = [i | i <- [0..d-1], any (\j -> vec VU.! (enc i j) == dMax) [0..d-1]]
  vert =  [j | j <- [0..d-1], any (\i -> vec VU.! (enc i j) == dMax) [0..d-1]]

  gap ps = maximum $ zipWith (-) (tail ps ++ [d + head ps]) ps

  ans = ((sqrtP dMax) - 1) * d + (d - min (gap horiz) (gap vert))
  
sqrtP :: Int -> Int
sqrtP x | y * y == x = y
        | otherwise  = y+1
  where y = floor $ sqrt (fromIntegral x)

readBInt :: B.ByteString -> Int
readBInt = fst . fromJust . B.readInt

tmain :: B.ByteString -> Int
tmain cont =
  let remLines0 = map B.words (B.lines cont)
      [bs_n,bs_d]:remLines1 = remLines0
      n = readBInt bs_n
      d = readBInt bs_d
      xys = map (\[x1,x2] -> (readBInt x1,readBInt x2)) remLines1
  in solve n d xys

outAnswer :: Int -> IO ()
outAnswer = putStrLn . show

main :: IO ()
main = outAnswer . tmain =<< B.getContents
