Problem Statement

A certain inn is closed on the first day of the month and on the 9th day, and accepts guest reservations for days 2 through 8.

Each guest makes a reservation for some range within the period from 00:00 on day 2 to 23:59 on day 8.

You are given the number $n$ of single rooms at the inn and the check-in and check-out reservation date-times, down to the minute, of $m$ guests.

Compute how many guests can stay when aiming to maximize the number of guests staying.

Because the room is cleaned after check-out, the next guest can enter only after an interval of 1 minute from the check-out time.

For example, a guest who reserved from 12:00 cannot enter a room whose guest checked out at 12:00. A reservation is valid from 12:01.

This problem is an original problem published on HackerRank, reposted and made public as a general problem with the permission of both HackerRank and yukicoder.

Input

$n$ $m$
$d_1$ $hh_1$:$mm_1$ $o_1$ $hho_1$:$mmo_1$
$\dots$
$d_i$ $hh_i$:$mm_i$ $o_i$ $hho_i$:$mmo_i$
$\dots$
$d_m$ $hh_m$:$mm_m$ $o_m$ $hho_m$:$mmo_m$

$n$ is the number of single rooms, and $m$ is the number of people with reservations.
$0 < n < 101$
$0 < m < 1001$
The following $m$ lines give the check-in and check-out date-times of the guests.
$d_i$ $hh_i$ $mm_i$ are the day, hour and minute of check-in.
$d_i$ is the day: $1 < d_i < 9$
$hh_i$ is the hour: $00 \leq hh_i < 24$
$mm_i$ is the minute: $00 \leq mmi < 60$
$o_i$ $hho_i$ $mmo_i$ are the day, hour and minute of check-out.
$o_i$ is the day: $1 < oi < 9$
$hho_i$ is the hour: $00 \leq hhoi < 24$
$mmo_i$ is the minute: $00 \leq mmoi < 60$
You may assume that the check-out is later than or at the same time as the check-in.
Even when a guest checks out at the same time as the check-in, the room can be reserved from one minute after the check-out.
In this case, you may assume that the guest uses the room for at most 1 minute and that the room is cleaned by a miraculous feat in the remaining time of that minute.
Output on one line $U$, the number of guests staying when the reservations are arranged so as to maximize the number of guests staying.

Output

$U$ Print a newline at the end.

Sample

1 3
3 10:00 3 10:00
3 10:00 3 10:00
3 10:01 3 10:02

2

2 7
3 12:30 4 15:30
3 16:30 3 16:30
3 16:31 4 15:29
4 15:30 7 15:30
2 02:00 3 15:29
3 15:10 4 15:29
3 12:47 4 14:27

5

3 11
3 12:30 4 15:30
4 15:31 5 16:20
5 16:21 6 17:30
3 12:30 4 15:30
4 17:30 6 03:30
7 12:10 8 23:59
2 14:40 4 15:30
5 16:40 7 12:20
8 00:00 8 17:54
8 17:54 8 17:55
2 12:00 7 03:30

10