{-# OPTIONS_GHC -O2 -funbox-strict-fields #-}
import           Control.Monad.ST                 (ST)
import           Control.Monad.State              (StateT (..), runStateT)
import           Data.Attoparsec.ByteString.Char8 (isSpace)
import           Data.Bits                        (shiftR)
import qualified Data.ByteString.Char8            as B
import qualified Data.ByteString.Unsafe           as B
import qualified Data.Vector.Unboxed              as V
import qualified Data.Vector.Unboxed.Mutable      as VM
import           Debug.Trace

main :: IO ()
main = do
  [n, m] <- map read . words <$> getLine
  abs <- V.unfoldrN n parseInt2 <$> B.getContents
  print $ solve n m abs

solve :: Int -> Int -> V.Vector (Int, Int) -> Int
solve _ m abs = go 0 0 abs'
  where
    abs' = sort' abs
    go n p abs
      | V.null abs = p
      | n + b >= m = p + (m - n) * a
      | otherwise = go (n + b) (p + b * a) (V.tail abs)
        where
          (a, b) = V.head abs

sort' :: (V.Unbox a, Ord a) => V.Vector a -> V.Vector a
sort' = V.modify (\v -> quicksort v 0 (VM.length v))

-- https://github.com/as-capabl/haskell-qsort-pfm/blob/master/src/UV.hs
quicksort :: (V.Unbox a, Ord a) => VM.STVector s a -> Int -> Int -> ST s ()
quicksort work iStart iEnd
    | iEnd - iStart <= 1 = return ()
    | otherwise = do
        pivot <- VM.unsafeRead work (((iEnd - iStart) `shiftR` 1) + iStart)
        med <- divide pivot iStart (iEnd - 1)
        quicksort work iStart med
        quicksort work med iEnd
  where
    divide pivot iS' iE'
        | iS' > iE' = return iS'
        | otherwise = do
            lower <- shrinkLower pivot iS' iE'
            higher <- shrinkHigher pivot lower iE'
            if lower >= higher
              then do
                return lower
              else do
                swapWork lower higher
                divide pivot (lower + 1) (higher - 1)

    shrinkLower pivot iS' iE'
        | iS' > iE' = return iS'
        | otherwise = do
            x <- VM.unsafeRead work iS'
            if x >= pivot
              then
                return iS'
              else
                shrinkLower pivot (iS' + 1) iE'

    shrinkHigher pivot iS' iE'
        | iS' > iE' = return iE'
        | otherwise = do
            x <- VM.unsafeRead work iE'
            if x <= pivot
              then
                return iE'
              else
                shrinkHigher pivot iS' (iE' - 1)

    swapWork i j = VM.unsafeSwap work i j

parseInt :: B.ByteString -> Maybe (Int, B.ByteString)
parseInt = B.readInt . B.dropWhile isSpace

parseInt2 :: B.ByteString -> Maybe ((Int, Int), B.ByteString)
parseInt2 = runStateT $
  (,) <$> StateT parseInt
  <*> StateT (B.readInt . B.unsafeTail)
