
{-# LANGUAGE BangPatterns #-}

import qualified Data.Vector.Unboxed as V
import Data.Array.IArray (listArray, accumArray, (!))
import Data.Array.MArray
import Data.Array.ST (STUArray, runSTUArray)
import Data.Array.Unboxed (UArray)
import Data.List (sortOn, sortBy, unfoldr, partition)
import Data.Char (isSpace)
import Control.Monad.ST (ST)
import Control.Monad.Trans.State (StateT(..))
import qualified Data.ByteString.Char8 as B

import qualified Data.IntMap as M

import Debug.Trace (trace)

-- utility functions

tr = id
trl l = id

--   Input functions
readInt = B.readInt . B.dropWhile isSpace

readInts :: Int -> B.ByteString -> [Int]
readInts n = take n . unfoldr readInt

readIntsV :: Int -> B.ByteString -> V.Vector Int
readIntsV n = V.unfoldrN n readInt

readIntsA :: Int -> B.ByteString -> UArray Int Int
readIntsA n bs = runSTUArray $ do
  arr <- newArray_ (0,n-1)
  go arr 0 bs
  return arr
  where
    go :: STUArray s Int Int -> Int -> B.ByteString -> ST s ()
    go arr i bs
      | i==n = return ()
      | otherwise = do
        let Just (x,bs') = readInt bs
        writeArray arr i x
        go arr (i+1) bs'

readTsV :: Int -> B.ByteString -> V.Vector (Int,Int)
readTsV n = V.unfoldrN n $ runStateT ((,) <$> StateT readInt <*> StateT readInt)

readTs :: Int -> B.ByteString -> [(Int,Int)]
readTs n = take n . unfoldr readT where
  readT = runStateT ((,) <$> StateT readInt <*> StateT readInt)

readSushis :: Int -> B.ByteString -> [Sushi]
readSushis n = take n . unfoldr readSushi where
  readSushi = runStateT (Sushi <$> StateT readInt <*> StateT readInt)

-- main

data Sushi = Sushi
  { typ :: Int
  , del :: Int
  } deriving (Eq)

instance Show Sushi where 
  show (Sushi t d) = show (t,d)

instance Ord Sushi where
  compare (Sushi t1 d1) (Sushi t2 d2) = compare d1 d2

enumGs fixed canRemove [] base kind = [base + kind*kind]
enumGs fixed [] _ base kind = [base + kind*kind]
enumGs fixed canRemove@(r:rs) (s:ss) base kind
  | M.member (typ s) fixed = enumGs fixed canRemove ss base kind
  | otherwise
    = let !base' = tr $ base - r + (del s)
          kind' = kind + 1 
      in (base + kind*kind) : enumGs (M.insert (typ s) (del s) fixed) rs ss base' kind'

solv k ss = maximum $ enumGs fixed canRemove remain base kind
  where
    !(mostDelicious, remain) = tr $ splitAt k $ sortBy (flip compare) ss
    !(fixed, canRemove) = trl "(fixed, canRemove)" $ part mostDelicious M.empty []
    kind = M.size fixed
    !base = tr $ M.foldl' (+) 0 fixed + sum canRemove
    part [] m s = (m, s)
    part (x:xs) m s
      | M.member (typ x) m = part xs m (del x:s)
      | otherwise = part xs (M.insert (typ x) (del x) m) s

main = do
  [n,k] <- map read . words <$> getLine
  sushi <- sortBy (flip compare) . readSushis n <$> B.getContents
  print $ solv k sushi
