Задача №113526. Hawks
Королевские Железные Дороги (КЖД) готовятся открыть новый, скоростной, маршрут из столицы в соседний город NN и обратно. Новые поезда будут добираться до места назначения втрое быстрее обычных ночных поездов. Конкурс на поставку новых составов выиграла зарубежная компания «MacroHard» — производитель локомотивов «Hawk», которые будут использоваться в королевстве под локализованным названием «Ястреб». Расписание уже готово, но до сих пор не решен вопрос, сколько именно составов нужно, чтобы его выполнить. Не требуется покупать по составу на каждый рейс, поскольку поезд, прибывший на станцию, может выполнить и обратный рейс. КЖД обратились к вам и просят написать программу, способную рассчитать минимально необходимое количество поездов на один день. Расписание состоит из N 1 рейсов из столицы в город NN и N 2 обратных рейсов. Для каждого рейса известно время отправления и время прибытия — с точностью до минуты. Любой рейс полностью выполняется в течение одних календарных суток (с 00: 00 до 23: 59 включительно) — то есть никакой рейс не прибывает на следующий день после отправления. Каждый рейс занимает как минимум одну минуту, то есть ни один поезд не прибывает на станцию назначения в ту же минуту, в которую он отправился . КЖД настолько эффективны, что после прибытия поезд готов в ту же минуту отправиться в обратный рейс. Одновременно на станции может находиться, отправляться или прибывать любое количество поездов. Руководство КЖД не одобряет холостые поездки, поэтому поезда не могут перемещаться вне расписания в течение дня. Отметим, что вам не нужно учитывать подготовку к выполнению расписания следующего дня — к моменту начала следующих суток железнодорожники способны обеспечить любое распределение составов по станциям, независимо от того, как они были распределены к концу предыдущих.
В первой строке находится число N 1 (1 ≤ N 1 ≤ 100000) — количество рейсов из столицы в город NN. В следующих N 1 строках находятся описания рейсов, по одному на строке: время прибытия и время отправления, разделенные дефисом («-»). И время прибытия, и время отправления записаны в формате HH : MM ,где HH — час (число от 0 до 23, при необходимости, дополненное ведущим нулем до двух цифр), MM — минута (число от 0 до 59, при необходимости, дополненное ведущим нулем до двух цифр). В N 1 + 2 - й строке находится число N 2 (1 ≤ N 2 ≤ 100000) — количество обратных рейсов: из города NN в столицу. На следующих N 2 строках находятся описания этих рейсов в том же формате.
Выведите единственное число — минимально возможное количество составов, которое нужно для выполнения расписания.
В первом примере семь поездов могут выполнить рейсы, например, следующим образом: 1. обратно 6:35, туда 19:00
2. туда 6:45, обратно 11:00
3. обратно 7:15, туда 20:08
4. туда 7:36, обратно 15:40
5. обратно 14:00
6. обратно 18:35
7. обратно 20:20.
Во втором примере один поезд может выполнить все рейсы.
4 06:45-10:20 07:36-11:26 19:00-22:35 20:08-23:58 7 06:35-10:10 07:15-11:10 11:00-14:48 14:00-17:48 15:40-19:28 18:35-22:23 20:20-23:55
7
2 10:00-12:00 15:00-17:00 2 12:30-14:30 17:30-19:30
1