Телохранители
Встречали ли вы когда-нибудь членов десяти европейских королевских домов, аргентинскую футбольную команду вместе с их тренером Диего Марадоной или всех лауреатов премий Тьюринга и Филдса? Мы пригласили множество знаменитостей со всего мира на церемонию закрытия 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" в противном случае (кавычки для ясности).