import qualified Data.Text as T
import qualified Data.Text.IO as T
import qualified Data.Text.Read as T
import Data.Tuple (swap)
import Data.List (sortBy)
import Data.Function (on)
import qualified Data.IntMap as IM

main :: IO ()
main = do
  [n, k] <- map unsafeTextToInt . T.words <$> T.getLine :: IO [Int]
  let
    maxSP :: [(Int, Int)] -> Int
    maxSP dts = snd . snd . snd . foldr step ((cs0, l0), (sf, ((dp0, tp0), sp0))) $ pf
      where
        (pf, sf) = splitAt k dts :: ([(Int, Int)], [(Int, Int)])
        cs0 = IM.fromListWith (+) . map (flip (,) 1 . snd) $ pf :: IM.IntMap Int
        l0 = n - length pf :: Int
        dp0 = sum . map fst $ pf :: Int
        tp0 = IM.size cs0 :: Int
        sp0 = dp0 + tp0 ^ 2 :: Int
        step :: (Int, Int) -> ((IM.IntMap Int, Int), ([(Int, Int)], ((Int, Int), Int))) -> ((IM.IntMap Int, Int), ([(Int, Int)], ((Int, Int), Int)))
        step _ r@((_, 0), _)                                                        = r
        step (_, t) r@((cs, _), _) | cs IM.! t == 1                                 = r
        step dt ((cs, l), ((_, t') : dts', dptpsp)) | IM.findWithDefault 0 t' cs /= 0 = step dt ((cs, pred l), (dts', dptpsp))
        step (d, t) ((cs, l), ((d', t') : dts', ((dp, tp), sp)))                          = ((cs', pred l), (dts', ((dp', tp'), sp')))
          where
            cs' = IM.insert t' 1 . IM.adjust pred t $ cs :: IM.IntMap Int
            dp' = dp - d + d' :: Int
            tp' = succ tp :: Int
            sp' = max sp (dp' + tp' ^ 2) :: Int
  tds <- sequence . replicate n $ unsafeListToPair . map unsafeTextToInt . T.words <$> T.getLine :: IO [(Int, Int)]
  let
    dts = sortBy (flip compare `on` fst) . map swap $ tds :: [(Int, Int)]
  print . maxSP $ dts

unsafeListToPair :: [a] -> (a, a)
unsafeListToPair [x, y] = (x, y)

unsafeTextToInt :: T.Text -> Int
unsafeTextToInt s = case T.signed T.decimal s of
  Right (n, _) -> n
