705. Рейсы между офисами

Не решаласьЛёгкая

У компании открылся второй офис и для перемещения сотрудников между офисами было решено организовать автобусные рейсы, которые будут ездить по расписанию из первого офиса во второй и обратно. Расписание уже готово, но непонятно, каким минимальным количеством автобусов удастся обслужить все рейсы.

Расписание состоит из N N рейсов из первого офиса во второй и M M обратных рейсов. Для каждого рейса известно время отправления и время прибытия с точностью до минуты. Любой рейс полностью выполняется в течение одних календарных суток (с 00:00 до 23:59 включительно), никакой рейс не прибывает на следующий день после отправления. Каждый рейс занимает как минимум одну минуту, то есть ни один рейс не прибывает к офису назначения в ту же минуту, в которую он отправился. После прибытия автобус готов в ту же минуту отправиться в обратный рейс. Одновременно возле офиса может находиться, отправляться или прибывать любое количество автобусов. Автобусы не могут перемещаться вне расписания в течение дня. Вам не нужно учитывать подготовку к выполнению расписания следующего дня — необходимо только определить минимальное количество автобусов для обслуживания рейсов в течение одного дня.

Формат ввода

В первой строке находится число N N ( 1   ≤ N ≤   100000 1 \le N \le 100000 ) — количество рейсов из первого офиса во второй. В следующих N N \ строках находятся описания рейсов, по одному на строке: время отправления и время прибытия, разделенные дефисом («-»).

И время прибытия, и время отправления записаны в формате HH:MM, где HH — час (число от 0 до 23, при необходимости, дополненное ведущим нулем до двух цифр), MM — минута (число от 0 до 59, при необходимости, дополненное ведущим нулем до двух цифр).

В N +   2 N + 2 -й строке находится число M M ( 1   ≤ M ≤   100000 1 \le M \le 100000 ) — количество рейсов из второго офиса в первый. В следующих M M строках находятся описания этих рейсов в том же формате.

Формат вывода

Выведите единственное число — минимально возможное количество автобусов, достаточное для обслуживания всех рейсов.

Ограничения

Ограничение времени
4 с
Ограничение памяти
256 МБ

Примеры

Пример 1

Ввод
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

Ввод
2
10:00-12:00
15:00-17:00
2
12:30-14:30
17:30-19:30
Вывод
1

Пример 3

Ввод
2
10:10-10:11
10:10-10:11
2
10:11-10:12
10:11-10:12
Вывод
2

Теги

18.1.8
Нужно войти, чтобы отправить решение.Войти