{-# LANGUAGE BangPatterns #-}

import qualified Data.List as L
import           Data.Set  as Set

import Data.Function (on)

import Control.Applicative
import Control.Monad       (replicateM)

main :: IO ()
main = do
    [n, k] <- getSeq
    ps     <- replicateM n getLine
    print $ solve k ps

solve :: Int -> [String] -> Int
solve k ps = inner bag id
  where
    set = Set.fromList ps
    bag = L.sort $ fmap (liftA2 (,) L.length L.head) <$> L.group $ L.head <$> Set.toList set
    inner :: [(Int, Char)] -> (Int -> Int) -> Int
    inner !bag cont
        | r /= 0    = cont 0
        | otherwise = inner xs (cont . succ)
      where
        (r, xs) = L.foldr f (k, []) bag
        f (n, c) (k, !xs)
          | k == 0    = (     0, (     n, c) : xs)
          | n == 1    = (pred k,               xs)
          | otherwise = (pred k, (pred n, c) : xs)

getSeq  = fmap read . words <$> getLine
