В одном большом городе готовятся к открытию новой ветки наземного метро. Она пролегает между двумя городами в пригороде по разные стороны от самого города, но проходя через него насквозь. Такую модель наземного метро назвали Городские центральные диаметры (ГЦД).
В рамках подготовки к запуску ГЦД было разработано специальное расписание, содержащее n рейсов в одном направлении и m рейсов в обратном. Для каждого рейса определены a
i - время отправления с первой конечной станции и b
i - время прибытия на вторую конечную станцию, для обратных рейсов c
j - время отправления со второй станции и d
j - время прибытия на первую станцию. Времена измеряются в минутах от начала дня. Внутри большого города поезда могут
передвигаться по различным маршрутам, поэтому поезд, отправившийся позже какого-то другого поезда, может прибыть раньше него.
Проекты такого масштаба ещё не запускались, а значит, будут происходить непредвиденные события и поезда будут задерживаться. Аналитики компании, обслуживающей ГЦД, посчитали, что при любых обстоятельствах поезд может опоздать на конечную станцию не более чем на t минут. Поезд может отправиться выполнять следующий рейс сразу же, как только закончил предыдущий.
Компании поручено во что бы то ни стало обеспечить выполнение каждого рейса. Определите, какое минимальное количество поездов необходимо иметь, чтобы ни один рейс гарантированно не был отменён даже в случае возможных задержек всех поездов. Поезда обязаны отправляться от
начальных станций строго по расписанию.
В начале и в конце дня поезда могут находиться на любой из станций. Перемещаться между станциями во время дня, кроме как по данному расписанию, поезда не могут.
Формат входных данных
Первая строка входных данных содержит максимальное время задержки при выполнении рейса t, 0 <= t <= 10
9.
Следующая строка содержит число n - количество рейсов в расписании в одну сторону, 0 <= n <= 100. Следующие 2n строк содержат числа a
1, b
1, a
2, b
2, ..., a
n, b
n - время отправления поездов от первой станции и время их прибытия на вторую станцию, 0 <= a
i < b
i <= 10
9.
Следующая строка содержит число m - количество поездов в расписании в обратную сторону, 0 <= m <= 100. Следующие 2m строк содержат время отправления c
j и прибытия d
j поездов в обратном направлении в аналогичном формате, 0 <= cj < dj <= 10
9.
Поезда в расписании перечислены в произвольном порядке, не обязательно в порядке возрастания времени.
Формат выходных данных
Программа должна вывести одно целое число - минимальное количество поездов, необходимое для выполнения данного расписания.
| Ввод |
Вывод |
4
2
3
8
5
10
1
11
15 |
3 |
1
2
15
18
7
9
2
11
14
1
3 |
1 |