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)] -> Q
    initialize = go k . (Q IS.empty 0 0 [])
      where
        go :: Int -> Q -> Q
        go 0 q = q
        go c (Q us dp tp ds ((d, t) : dts))
            | IS.member t us = go c' (Q us dp' tp ds' dts)
            | otherwise      = go c' (Q 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 ::  Q -> Int
    maxSP (Q us0 dp0 tp0 ds0 cs0) = go (Q us0 dp0 tp0 ds0 cs0) sp0
      where
        sp0 = dp0 + tp0 ^ 2 :: Int
        go :: Q -> Int -> Int
        go (Q us dp tp ds@(d' : ds') ((d, t) : cs')) sp
            | IS.member t us = go (Q us dp tp ds cs') sp
            | otherwise      = go (Q us' dp' tp' ds' cs') 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
  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

data Q = Q !IS.IntSet !Int !Int ![Int] ![(Int, Int)]

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
