Bodyguards

Time limit1sMemory limit128 MB

Summary

Given row and column sums compressed into groups, decide if a 0/1 matrix exists matching those row and column sums (Gale-Ryser feasibility with huge grouped counts).

Level: Hard8 of 10
Topics: Greedy, Combinatorics, Math
Solved: No attempts yet

Problem

The auditorium for a closing ceremony has many seats arranged in a large rectangular grid. For security, an expert has fixed the exact number of bodyguards that must be seated in each row and in each column.

You are given the required number of bodyguards for every row and every column, provided in the compressed (grouped) form described below. The auditorium starts empty and each seat may hold at most one bodyguard. Decide whether it is possible to seat the bodyguards so that every row and every column contains exactly its required number of bodyguards.

Input

The input first describes the rows.

The first line contains an integer $R$ , the number of row groups.
Each of the next $R$ lines contains two integers $b$ and $n$ : every row in this group requires exactly $b$ bodyguards, and the group consists of $n$ rows.

The input then describes the columns.

The next line contains an integer $C$ , the number of column groups.
Each of the next $C$ lines contains two integers $b$ and $n$ : every column in this group requires exactly $b$ bodyguards, and the group consists of $n$ columns.

Output

Print a single line containing 1 if the requirements can be satisfied, or 0 otherwise.

Constraints

The total number of bodyguards required by the rows equals the total required by the columns, and this total is at most $10^{18}$ .
Every integer in the input is a positive integer not exceeding $10^9$ .
$1 \le R, C \le 200\,000$ .

Examples2

Example 1
Input
```
2
2 1
1 2
1
2 2
```
Expected output
```
1
```
Example 2
Input
```
2
3 2
1 1
2
3 2
1 1
```
Expected output
```
0
```