import Data.Char
import Data.List
import qualified Data.ByteString.Char8 as B
import qualified Data.Map as M
main=print.solve.map(unfoldr$B.readInt.B.dropWhile isSpace).B.lines=<<B.getContents
solve([n,c]:stcs)=M.foldr(+)0.foldl f M.empty.sort$map(\[s,t,c]->(t,s))stcs
f m(t,s)=M.insertWith(+)t 1$case M.lookupLT s m of
  Just(k,v) -> if v>1 then M.insert k(v-1)m else M.delete k m
  Nothing -> m