说明

时间限制：1 Sec 内存限制：256 MB 输入文件：hotel.in 输出文件：hotel.out

某旅馆将每月月初和每月 $9$ 日定为休息日，仅接受 $2$ 日至 $8$ 日的客人预订。

客人可预订的时间范围为 $2$ 日 $00:00$ 至 $8$ 日 $23:59$。

现给定旅馆的单人单间数量 $n$，以及 $m$ 位客人的入住、退房的预约日期和时间（精确到分钟）。

请你计算，在以最大化入住人数为目标的前提下，该旅馆最多可容纳多少位客人入住。

补充规则

退房后需要对房间进行清扫，因此下一位客人的入住时间，必须与上一位客人的退房时间间隔至少 $1$ 分钟。

例如，若某客人在 $12:00$ 退房，那么其他客人无法在 $12:00$ 预订该房间，最早的有效预订时间为 $12:01$。

输入格式

第一行两个整数 $n$ 和 $m$，分别表示单人单间的数量和预约客人的数量。

接下去 $m$ 行，每行表示一位客人的入住与退房时间，格式为 $d_i$ $hh_i$:$mm_i$ $o_i$ $hho_i$:$mmo_i$。其中 $d_i$ 表示入住日期，$hh_i$ 表示小时数，$mm_i$ 表示分钟数，$o_i$ 表示退房日期，$hho_i$ 表示小时数，$mmo_i$ 表示分钟数。

日期和时间保证合法，也就是 $1 \lt d_i,o_i \lt 9$、$00 \le hh_i,hho_i \lt 24$、$00 \le mm_i,mmo_i \lt 60$。

保证退房时间不早于入住时间。

若入住时间与退房时间完全相同，该房间最早可在退房时间的 $1$ 分钟后重新预订。这种情况下，视为客人仅使用了房间 $1$ 分钟以内的时间，剩余的 $1$ 分钟可完成房间清扫。

输出格式

输出一行一个整数 $U$，表示通过合理安排预约可容纳的最大入住人数。

样例

样例 1

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

2

样例说明：

旅馆只有 $1$ 间房。

前两位客人的入住和退房时间都是 $3$ 日 $10:00$，该房间最早可在 $10:01$ 重新预订；第三位客人的入住时间为 $10:01$，因此最多可容纳 $2$ 位客人入住。

样例 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

样例说明：

合理安排 $2$ 间房的预约，最多可容纳 $5$ 位客人入住。

样例 3

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

数据范围

对于 8% 的数据，满足 $n=1$。

另有 12% 的数据，满足 $n \le 3$。

对于 100% 的数据，满足 $1 \le n \le 100$，$1 \le m \le 1000$。