P6519 [CEOI 2010] bodyguards (day1)

In a matrix, you need to place a required number of bodyguards in certain rows and columns. Each cell can contain at most one bodyguard. Determine whether there exists an arrangement such that some rows and columns contain exactly the required number of bodyguards.

The first line contains an integer $R$, meaning there are $R$ constraints on rows. The next $R$ lines each contain two integers $a, b$, meaning there are $b$ rows that must contain exactly $a$ bodyguards. The next line contains an integer $C$, meaning there are $C$ constraints on columns. The next $C$ lines each contain two integers $x, y$, meaning there are $y$ columns that must contain exactly $x$ bodyguards.

Output one number in a single line. If such an arrangement exists, output `1`; otherwise output `0`.

#### Explanation of Sample 1 One row must contain two bodyguards, and two rows must contain one bodyguard; two columns must contain two bodyguards. One possible arrangement is: ``` XX X. .X ``` Here, `X` represents a bodyguard and `.` represents an empty cell. #### Explanation of Sample 2 Two rows must be filled entirely with bodyguards, but one column is required to contain only one bodyguard, so it is impossible. Therefore, there is no solution. #### Constraints - For $50\%$ of the testdata, it is guaranteed that $R, C \le 2000$, and there are at most $10^6$ bodyguards. - For $100\%$ of the testdata, the total number of bodyguards is at most $10^{18}$. All numbers are positive integers not exceeding $10^9$, and $1 \le R, C \le 2 \times 10^5$. #### Notes **Translated from [CEOI 2010](http://ceoi2010.ics.upjs.sk/Contest/Tasks) day 1 *[T3 bodyguards](https://people.ksp.sk/~misof/ceoi2010/bod-eng.pdf)***. The translation copyright belongs to the problem provider @[ShineEternal](https://www.luogu.com.cn/user/45475). Reposting without permission is prohibited. Translated by ChatGPT 5