3315번 - Bodyguards 다국어

Have you ever met the members of the ten European royal houses, the Argentinian football team including their coach Diego Maradona, or all of the Turing and Fields medal prize winners? We have invited many celebrities from all over the world to the CEOI 2010 closing ceremony. Unfortunately, very few of them responded to our invitation, and those who did, politely rejected. Nevertheless, do not forget to bring your camera to the ceremony, one never knows who might turn up!

As you can imagine, the security of the guests is of utmost importance. The problem is how to seat their bodyguards in the audience so that maximal security is guaranteed.

The auditorium contains many seats, arranged into a large grid. Based on the safety regulations a security expert has determined necessary bodyguard counts for each row and each column of the auditorium.

You are given the required number of bodyguards for each row and column of the auditorium. This information is given in a compressed form as explained below. Determine whether it is possible to place the bodyguards in such a way that in each row and each column we would have exactly the required number of bodyguards.

Assume that the auditorium is initially empty, i.e., you may seat bodyguards wherever you wish. Each seat may only be occupied by a single bodyguard.

The input begins with the description of the rows. The first line of the input contains one positive integer R: the number of groups of rows. R lines follow. Each of these lines contains 2 positive integers: the required number of bodyguards in each row of the group and the number of rows that form the group.

followed by the description of column groups. The next line contains one positive integer C: the number of groups of columns. C lines follow. Each of these lines contains 2 positive integers: the required number of bodyguards in each column of the group and the number of columns that form the group.

Output a single line with the number "1" if the constraints are satisfiable and the number "0" otherwise (quotes for clarity).

You may assume that the total number of bodyguards required by row constrains is the same as the total number of bodyguards required by column constraints. You may assume that this total number of bodyguards is at most 10¹⁸.

You may assume that all numbers are positive integers that do not exceed 1 000 000 000.

You may assume that 1 ≤ R, C ≤ 200 000.