問題文

ある旅館では月初めと9日目を休みとし、2日から8日までの客の予約をとる。

客は2日目の00時00分から8日目の23時59分までのいずれかの範囲内で予約をとる。

旅館の1人用個室数$n$、$m$人の客のチェックインとチェックアウトの予約日時が分単位までで与えられる.

泊まる客の人数を最大化することを目指した時何人泊まれるか算出してほしい。

チェックアウト後、部屋の清掃があるため次の客が入れるのはチェックアウト時刻から1分の間隔は空ける必要があるとする。

例えば客が12時にチェックアウトした部屋は12時に予約した客はその部屋に入れない。 12時1分から予約が有効であるとする。

この問題はHackerRankで公開した自作問題をHackerRank公式,yukicoder公式両方の許可を得て転載し一般問題とし公開となっています。

入力

$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$は一人用部屋の個数、$m$は予約の人数。
$0 < n < 101$
$0 < m < 1001$
続く$m$行は顧客のチェックインとチェックアウトの日時である。
$d_i$ $hh_i$ $mm_i$はチェックインの日時分である。
$d_i$は日付 $1 < d_i < 9$
$hh_i$は時間 $00 \leq hh_i < 24$
$mm_i$は分　$00 \leq mmi < 60$
$o_i$ $hho_i$ $mmo_i$はチェックアウトの日時分である。
$o_i$は日付　$1 < oi < 9$
$hho_i$は時間 $00 \leq hhoi < 24$
$mmo_i$は分　$00 \leq mmoi < 60$
チェックアウトはチェックインより後か同じ時刻と仮定してよい。
チェックインと同じ時刻にチェックアウトする場合も、チェックアウトした一分後からその部屋の予約が可能であるとする。
この場合客は１分以下だけ部屋を使い、１分の残り時間で神業で部屋の清掃が行われたと仮定してよい。
出力$U$は泊まる人数を最大化するよう予約をやりくりした時の宿泊人数を一行に答えよ。

出力

$U$ 最後に改行してください。

サンプル

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