module ABC116D where

import Control.Monad
import Data.List
import Data.Map (Map,(!))
import qualified Data.Map as M
import Data.Set (Set)
import qualified Data.Set as S

type Sushi = (Type,Deli)
type Type = Int
type Deli = Integer
type Score = Integer

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

solve :: Int -> Int -> [Sushi] -> Score
solve n k sushis = maximum $ go toTake taken removable howRem delisum types
  where
  go :: [Sushi] -> Set Type -> Map Type [Deli] -> [Type] -> Deli -> Integer -> [Score]
  go [] _ _ _ delisum types = [score delisum types]
  go _ _ _ [] delisum types = [score delisum types]
  go ((t,d):toTake) taken removable (r:howRem) delisum types
    | S.notMember t taken = score delisum types
      : go toTake (S.insert t taken) (M.adjust tail r removable)
        howRem (delisum - head (removable!r) + d) (types + 1)
    | otherwise = go toTake taken removable (r:howRem) delisum types
  score :: Deli -> Integer -> Score
  score delisum types = delisum + types*types
  -- Initial Values
  toTake = filter (null.(eats!).fst) remainings
  (delicious,remainings) = splitAt k sushis
  taken = S.empty
  removable = M.filter (\ds -> not (null ds || (null.tail) ds)) eats
  (eats, howRem, types) = foldl folder (M.empty, [], 0) delicious
  folder :: (Map Type [Deli], [Type], Integer) -> Sushi -> (Map Type [Deli], [Type], Integer)
  folder (eats, howRem, types) (t,d)
    | null (eats!t) = (M.adjust (d:) t eats, howRem, types+1)
    | otherwise     = (M.adjust (d:) t eats, t:howRem, types)
  delisum = sum $ map snd delicious