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

type Sushi = (Int,Integer)
type EatMap = Map Int [Integer]

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

solve :: Int -> Int -> [Sushi] -> Integer
solve n k sushi = maximum $ go change eatMap howTake x ds S.empty
  where
  (eat,remain) = splitAt k sushi
  change = filter (\(t,_) -> M.notMember t eatMap') remain
  eatMap = M.filter (not.null.tail) eatMap'
  eatMap' = M.filter (not.null) eatMap''
  ds = sum $ map snd eat
  (eatMap'',howTake,x) = foldl f (zeroMap,[],0) eat
  zeroMap = M.fromDistinctAscList $ zip [1..n] $ repeat []
  f :: (EatMap, [Int],Integer) -> Sushi -> (EatMap, [Int],Integer)
  f (map,hows,x) (t,d)
    | null (map!t) = (M.adjust (d:) t map, hows, x+1)
    | otherwise  = (M.adjust (d:) t map, t:hows, x)
  go :: [Sushi] -> EatMap -> [Int] -> Integer -> Integer -> S.Set Int -> [Integer]
  go [] _ _ x ds _ = [score ds x]
  go _ _ [] x ds _ = [score ds x]
  go ((t,d):rs) eatMap (h:hs) x ds set
    | S.notMember t set = score ds x : go rs (M.adjust (d:) t $ M.adjust tail h eatMap) hs (x+1) (ds-head(eatMap!h)+d) (S.insert t set)
    | otherwise = go rs eatMap (h:hs) x ds set
  score :: Integer -> Integer -> Integer
  score ds x = ds + x*x