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.IntSet as IS

main :: IO ()
main = do
  [n, k] <- map unsafeTextToInt . T.words <$> T.getLine :: IO [Int]
  let
    initialize :: [(Int, Int)] -> (IS.IntSet, Int, Int, [Int], [(Int, Int)])
    initialize = go k IS.empty 0 0 []
      where
        go :: Int -> IS.IntSet -> Int -> Int -> [Int] -> [(Int, Int)] -> (IS.IntSet, Int, Int, [Int], [(Int, Int)])
        go 0 us0 dp0 tp0 ds0 cs0 = (us0, dp0, tp0, ds0, cs0)
        go c us dp tp ds ((d, t) : dts)
            | IS.member t us = go c' us dp' tp ds' dts
            | otherwise      = go c' us' dp' tp' ds dts
          where
            c' = pred c :: Int
            us' = IS.insert t us :: IS.IntSet
            dp' = dp + d :: Int
            tp' = succ tp :: Int
            ds' = d : ds :: [Int]
    maxSP ::  (IS.IntSet, Int, Int, [Int], [(Int, Int)]) -> Int
    maxSP (us0, dp0, tp0, ds0, cs0) = go cs0 us0 ds0 dp0 tp0 sp0
      where
        sp0 = dp0 + tp0 ^ 2 :: Int
        go :: [(Int, Int)] -> IS.IntSet -> [Int] -> Int -> Int -> Int -> Int
        go ((d, t) : cs') us ds@(d' : ds') dp tp sp
            | IS.member t us = go cs' us ds dp tp sp
            | otherwise      = go cs' us' ds' dp' tp' sp'
          where
            us' = IS.insert t us :: IS.IntSet
            dp' = dp - d' + d :: Int
            tp' = succ tp :: Int
            sp' = max sp (dp' + tp' ^ 2) :: Int
        go [] _ _ _ _ sp = sp
        go _ _ [] _ _ sp = sp
  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 . initialize $ 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
