import Control.Monad
import Data.List
import Data.Maybe

main = do
  [n,k] <- map read.words <$> getLine
  sushi <- replicateM n $ (\[a,b] -> (a,b)).(map read.words) <$> getLine
  print $ solve n k (sortBy (\(_,a) (_,b) -> compare a b) sushi)

solve n k sushi = go (reverse h) t
  where
  (h,t) = splitAt (n-k) sushi
  go [] eat = ds + x*x
    where
    ds = sum $ map snd eat
    x = fromIntegral.length $ nubBy (\(a,_) (b,_) -> a == b) eat
  go (s@(t,_):ss) eat
    | new = max (go ss eat) (go ss (s:left))
    | otherwise = go ss eat
    where
    (new,left) = inner eat
    inner [] = (False,[])
    inner (s@(t',_):ss)
      | t' /= t && any ((t' ==).fst) ss = (True, ss)
      | otherwise = (it, s:is)
      where (it,is) = inner ss
