def schedule_problem_legacy(brackets)
    bb = brackets.sort
    ans = []
    bb.each do |b|
        ans << b if ans.empty? || ans.last[0] < b[1]
    end
    return ans
end


def schedule_problem(brackets, slotsize = 1)
    bb = brackets.sort
    ans = []
    slots = [-1]*slotsize
    bb.each do |b|
        able = slots.select{|t| t < b[1] }.max
        if able
            slots[slots.index(able)] = b[0]
            ans << b
        end
    end
    return ans
end




n, m = gets.split.map(&:to_i)
brackets = []
m.times do
    z = gets.scan(/(\d+) (\d+):(\d+)/)
    brackets << z.map{|t| t.map!(&:to_i); t[0]*1440+t[1]*60+t[2]}.reverse
end

ans = schedule_problem(brackets, n).size
p ans