1494: Діаметральне метро


Submit solution


Points:20
Time limit:1.0s
Memory limit:62M
Author:

Problem types

В одному великому мiстi готуються до вiдкриття нової гiлки наземного метро. Вона пролягає мiж двома мiстами в передмiстi по рiзнi боки вiд самого мiста i проходить через нього наскрiзь. Таку модель наземного метро назвали Мiськi центральнi дiаметри (МЦД).

В рамках пiдготовки до запуску МЦД було розроблено спецiальний розклад, що мiстить n рейсiв в одному напрямку i m рейсiв в зворотному. Для кожного рейсу визначенi a_i - час вiдправлення з першої кiнцевої станцiї i b_i - час прибуття на другу кiнцеву станцiю, для зворотних рейсiв c_j - час вiдправлення з другої станцiї i d_j - час прибуття на першу станцiю. Часовi промiжки вимiрюються в хвилинах вiд початку дня.

Всерединi великого мiста поїзди можуть пересуватися по рiзних маршрутах, тому поїзд, що вiдправився пiзнiше якогось iншого поїзда, може прибути ранiше за нього. Проекти такого масштабу ще не запускалися, а значить, будуть вiдбуватися непередбаченi подiї та поїзди будуть затримуватися. Аналiтики компанiї, яка обслуговує МЦД, порахували, що при будь-яких обставинах поїзд може запiзнитися на кiнцеву станцiю не бiльше нiж на t хвилин. Поїзд може вiдправитися виконувати наступний рейс вiдразу ж, як тiльки закiнчив попереднiй.

Компанiї доручено за будь-яку цiну забезпечити виконання кожного рейсу. Визначте, яку мiнiмальну кiлькiсть поїздiв необхiдно мати, щоб жоден рейс гарантовано не був скасований навiть в разi можливих затримок всiх поїздiв. Потяги зобов’язанi вирушати вiд початкових станцiй строго за розкладом. На початку i в кiнцi дня поїзди можуть перебувати на будь-якiй станцiї. Перемiщатися мiж станцiями пiд час дня, окрiм як за розкладом, потяги не можуть.

Формат вхідних даних

Перший рядок вхiдних даних мiстить максимальний час затримки при виконаннi рейсу t, 0 <= t <= 10^9.

Наступний рядок мiстить число n - кiлькiсть рейсiв в розкладi в одну сторону, 0 <= n <= 100.

Наступнi 2n рядкiв мiстять числа a_1 , b_1 , a_2 , b_2 , ..., a_n , b_n - час вiдправлення поїздiв вiд першої станцiї i час їх прибуття на другу станцiю, 0 <= a_i < b_i <= 10^9.

Наступний рядок мiстить число m - кiлькiсть поїздiв в розкладi в зворотному напрямку, 0 <= m <= 100.

Наступнi 2m рядкiв мiстять час вiдправлення c_j i прибуття d_j поїздiв в зворотному напрямку в аналогiчному форматi, 0 <= c_j < d_j <= 10^9.

Потяги в розкладi розмiщенi в довiльному порядку, не обов’язково в порядку зростання часу.

Формат вихідних даних

Програма повинна вивести одне цiле число - мiнiмальну кiлькiсть поїздiв, необхiдних для виконання даного розкладу.

Система оцiнки

Розв’язки, якi правильно працюють для випадку, коли значення t, a_i , b_i , c_j , d_j не перевищують 100, оцiнюватимуться в 40 балiв.

Розв’язки, якi правильно працюють для випадку, коли значення t, a_i , b_i , c_j , d_j не перевищують 10^5, оцiнюватимуться в 70 балiв.

Приклад вхідних даних

4
2
3
8
5
10
1
11
15

Приклад вихідних даних

3

Приклад вхідних даних

1
2
15
18
7
9
2
11
14
1
3

Приклад вихідних даних

1

Пояснення

У першому тестi t = 4 , n = 2 , m = 1. Перший поїзд їде в момент часу a_1 = 3 i прибуває в b_1 = 8. Другий поїзд вiдправляється в момент часу a_2 = 5 i прибуває в b_2 = 10. З другої станцiї до першої поїзд вiдправляється в c_1 = 11 i прибуває в d_1 = 15 . Перший поїзд не встигає виконати зворотний рейс, тому що вiн прибуває на другу станцiю за розкладом в 8, але може спiзнитися на 4 хвилини, тобто вiн зможе виконати зворотний рейс тiльки при вiдправленнi не ранiше 12 хвилини. Тому для реалiзацiї розкладу необхiдний третiй поїзд.

У другому тестi t = 1 , n = 2 , m = 2. Поїзд по черзi виконує всi рейси. Спершу вiн виконує рейс вiд другої станцiї до першої - вiдправленням в c_2 = 1, прибуттям в d_2 = 3. Потiм рейс вiд першої станцiї до другої - вiдправленням a_2 = 7, прибуттям b_2 = 9. Далi виконує рейс вiд другої станцiї до першої - вiдправленням c_1 = 11, прибуттям d_1 = 14 . Нарештi, вiн виконує рейс вiд першої станцiї до другої - вiдправленням в a_1 = 15, прибуттям в b_1 = 18. Максимальний час затримки в дорозi дорiвнює 1, тому один потяг зможе виконати всi цi рейси.

Джерело: olympiads.ru


Comments

There are no comments at the moment.