Охоронці
Чи зустрічали ви коли-небудь членів десяти європейських королівських родин, аргентинську футбольну команду разом з їхнім тренером Дієго Марадоною, або всіх лауреатів премій Тюрінга та Філдса? Ми запросили багато знаменитостей з усього світу на церемонію закриття CEOI 2010. На жаль, дуже мало з них відповіли на наше запрошення, і ті, хто відповів, ввічливо відмовилися. Проте, не забудьте взяти з собою камеру на церемонію, ніколи не знаєш, хто може з'явитися!
Як ви можете уявити, безпека гостей є надзвичайно важливою. Проблема полягає в тому, як розсадити їхніх охоронців у залі так, щоб була гарантована максимальна безпека.
Аудиторія містить багато місць, розташованих у великій сітці. Виходячи з правил безпеки, експерт з безпеки визначив необхідну кількість охоронців для кожного рядка та кожного стовпця аудиторії.
Вам надано необхідну кількість охоронців для кожного рядка та стовпця аудиторії. Ця інформація надана у стислій формі, як пояснено нижче. Визначте, чи можливо розмістити охоронців таким чином, щоб у кожному рядку та кожному стовпці було точно необхідну кількість охоронців.
Припустимо, що аудиторія спочатку порожня, тобто ви можете розсадити охоронців де завгодно. Кожне місце може бути зайняте лише одним охоронцем.
Вхідні дані
Вхід починається з опису рядків. Перша строка вхідних даних містить одне додатне число R: кількість груп рядків. Далі йдуть R рядків. Кожен з цих рядків містить 2 додатних числа: необхідну кількість охоронців у кожному рядку групи та кількість рядків, що утворюють групу.
Далі йде опис груп стовпців. Наступна строка містить одне додатне число C: кількість груп стовпців. Далі йдуть C рядків. Кожен з цих рядків містить 2 додатних числа: необхідну кількість охоронців у кожному стовпці групи та кількість стовпців, що утворюють групу.
Обмеження
Ви можете припустити, що загальна кількість охоронців, необхідна за обмеженнями рядків, дорівнює загальній кількості охоронців, необхідній за обмеженнями стовпців. Ви можете припустити, що ця загальна кількість охоронців не перевищує 10^18.
Ви можете припустити, що всі числа є додатними цілими числами, які не перевищують 1000000000.
Ви можете припустити, що 1 ≤ R, C ≤ 200000.
Кілька партій тестових випадків, вартістю загалом 50 балів, задовольняють такі критерії:
загальна кількість рядків в аудиторії буде не більше 2000
загальна кількість стовпців в аудиторії буде не більше 2000
загальна кількість охоронців буде не більше 1000000.
У партії тестів вартістю ще 10 балів ми маємо R, C ≤ 100 у кожному тестовому випадку.
Вихідні дані
Виведіть один рядок з числом "1", якщо обмеження можна виконати, і число "0" в іншому випадку (лапки для ясності).