
import Data.Array (Array, listArray, (!))
import qualified Data.Set as S
import Data.Maybe (fromJust)

data Sushi = Sushi
  { t :: Int
  , d :: Int
  }
data DP = DP
  { getChoosed :: [Int]
  , getPoint :: Int
  , getKindNum :: Int
  }

dp f s e = result ! e where
  result = listArray (s,e) $ map nth [s..]
  nth i = f result i

add :: Array Int Sushi -> Int -> DP -> DP
add sushi x (DP xs point kind) = DP (x:xs) newPoint newKind where
  newSushi = sushi ! x
  newKind = if elem (t newSushi) (map (t . (sushi!)) xs) then kind else kind + 1
  newPoint = point + d newSushi + if kind == newKind then 0 else 2*kind+1

maxBy p x y
  | p x >= p y = x
  | otherwise  = y

solv :: Int -> Int -> Array Int Sushi -> Array Int (Maybe DP)
solv n k sushi = dp f 0 n where
  f :: Array Int (Array Int (Maybe DP)) -> Int -> Array Int (Maybe DP)
  f _ 0 = listArray (0,k) $ repeat $ Just $ DP [] 0 0
  f t i = listArray (0,k) $ (Just $ DP [] 0 0) : map (g t i) [1..k]

  g :: Array Int (Array Int (Maybe DP)) -> Int -> Int -> Maybe DP
  g t i k =
    let added = add sushi i <$> t!(i-1)!(k-1)
        notadded = t!(i-1)!k
    in
        maxBy (fmap getPoint) added notadded

mkSushi [t,d] = Sushi t d
main = do
  n:k:_ <- map read . words <$> getLine :: IO [Int]
  sushi <- listArray (1,n) . map (mkSushi . map read . words) . lines <$> getContents
  let result = solv n k sushi
  print . getPoint . fromJust $ result ! k
