Протяги і кролики#3214
Король Кролик — сильний і справедливий правитель. Рік за роком він підтримує країну на високому рівні розвитку, захищаючи її від нападів кенгуроїдів і хамстарів. Громадяни королівства люблять свого Короля. Прийшла весна, і Король повернувся з чергового походу.
Король любить весну й просить відкрити якомога більше вікон у головному коридорі свого замку. Це непросто, адже в замку багато вікон. Кролики-слуги не хочуть, щоб Король застудився, тому повинні відкрити вікна так, щоб у коридорі не було протягу.
Коридор можна уявити як дві паралельні стіни з вікнами. Кожне вікно задається двома координатами: початком і кінцем. Обидві стіни починаються в координаті й мають довжину . На першій стіні знаходиться N_1 вікон (вікна не перетинаються, але можуть торкатися), на другій стіні — N_2 вікон.
Протяг виникає, якщо є прямий шлях для вітру через коридор (вітер дме перпендикулярно до стін). Зокрема, якщо відкрито два вікна: на першій стіні й на другій, виникає протяг на проміжку . Для вікон і , а також і , протягу немає.
Яку максимальну кількість вікон можна відкрити?
Перший рядок містить три цілих числа, розділених пробілами: L, N_1, N_2 (1 \leq L \leq 100000, 0 \leq N_1, N_2 \leq L). Наступні N_1 рядків містять по два цілих числа — початкову й кінцеву координати вікна на першій стіні: (0 \leq b < e \leq L). Далі у такому ж форматі описані N_2 вікон на другій стіні.
Виведіть одне ціле число — максимальну кількість вікон, які можна відкрити так, щоб Король не застудився.
Приклад 1