Cram School Schedule

Time Limit : 5 sec, Memory Limit : 131072 KB

B: Cram School Schedule / 塾の時間割

物語

あなたは塾の経営者である.あなたの塾は個人授業制で1人の生徒と1人の先生で授業を行う.この塾の先生は非常に優秀で科目にかかわらずすべての授業を行うことができる.また,先生と生徒は非常にタフなので,出席できる授業には他の授業の出席状況にかかわらず,すべて出席することが可能である.例えば,同じ時間帯の授業に出席できる2人の生徒と4人の先生がいる場合は,その時間帯に2つの授業を行える.

あなたは来月の授業予定を立てなくてはいけないが,先生と生徒の人数が多いため予定を立てるのが非常に大変である.また,あなたはできるだけ多くの授業を行いたいと考えている.そのため,あなたは行える最大の授業数を求めるプログラムを作ることにした.

問題

先生の人数と,生徒の人数,それぞれの先生と生徒の予定がない時間帯,授業を行える時間帯が与えられる.それぞれの先生,または生徒について,予定がない時間帯が授業を行える時間帯を完全に被覆しているとき,その先生,または生徒はその授業に出席できる.それぞれの授業を行える時間帯では,出席できる先生と生徒からなるペアを複数作り,作ったペアの数だけの授業を同時に行うことができる.このときに行える最大の授業数を求めよ.

入力形式

入力データの形式は以下のように与えられる.

 授業が行える時間帯の情報
 n
 先生1の時間帯の情報
...
 先生nの時間帯の情報
 m
 生徒1の時間帯の情報
...
 生徒mの時間帯の情報

最初の1行には授業を行える時間帯の情報が与えられる.

続く1行には先生の人数 n (1 ≤ n ≤ 100) が与えられる.続く n 行の i 行目には i 番目の先生の予定がない時間帯の情報が与えられる.

続く1行には生徒の人数 m (1 ≤ m ≤ 100) が与えられる.続く m 行の i 行目には i 番目の生徒の予定がない時間帯の情報が与えられる.

各々の時間帯の情報は次の形式で与えられる.

k ah_1:am_1-bh_1:bm_1  . . .  ah_k:am_k-bh_k:bm_k

はじめに時間帯の数 k (1 ≤ k ≤ 100) が与えられ,空白区切りで k 個の時間帯が与えられる.i 番目の時間帯は ah_i:am_i-bh_i:bm_i の形式で与えられ,ah_i:am_i が開始時刻を表し,bh_i:bm_i が終了時刻を表す.ah_i, am_i, bh_i, bm_i はそれぞれ0詰め2桁で 0 ≤ ah_i, bh_i ≤ 23, 0 ≤ am_i, bm_i ≤ 59 を満たす整数である.

与えられるすべての時間帯について,開始時刻は終了時刻より真に早い.また,それぞれの時間帯の情報において,時間帯は早い時刻順に並んでおり,どの終了時刻も1つ後の時間帯の開始時刻より真に早い.

出力形式

行える授業の最大数を1行で出力せよ.

入力例1

2 10:00-11:30 12:00-13:00
2
1 10:00-15:00
2 09:00-12:00 18:10-18:55
2
2 10:00-13:00 15:30-16:40
3 06:00-08:00 12:00-13:10 15:00-17:00

出力例1

2

1つ目の時間帯と2つ目の時間帯で1つずつ授業を行うことで,2回の授業を行うことができる.

入力例2

2 07:00-08:30 10:00-12:00
3
3 08:30-09:00 11:05-15:05 23:10-23:55
2 09:00-12:00 17:45-18:55
1 08:00-10:00
2
2 07:20-11:00 12:30-17:05
3 07:48-08:51 11:22-16:15 17:02-17:59

出力例2

0

予定がない時間帯で07:00からの授業に間に合う先生と生徒のペアが存在しないので1つ目の時間帯は授業を行うことができない.また,2つ目の時間帯は2人目の先生が出席できるが,生徒は誰も出席できない.よって,2つ目の時間帯も授業を行うことができない.したがって,行える最大の授業数は0である.


Source: Ritsumeikan University Programming Camp 2015 , Problem set from Hokkaido University teams, Shiga, Japan, 2015-03-16