题目描述

在一个矩阵中，需要在一些行和列上安排目标数量的保镖。每个位置可以放置一名保镖。你需要求出能否安排出一种方案，使得一些行、列上恰好有目标数量的保镖？

输入格式

输入第一行一个整数 $R$，表示共有 $R$ 条行上的约束。

接下来的 $R$ 行，每行两个整数 $a,b$，表示有 $b$ 行需要恰好包含 $a$ 名保镖。

接下来的一行一个整数 $C$，表示共有 $C$ 条列上的约束。

接下来的 $C$ 行，每行两个整数 $x,y$，表示有 $y$ 列需要恰好包含 $x$ 名保镖。

输出格式

输出一行一个数字。如果存在这样的方案，输出 1；否则输出 0。

2
2 1
1 2
1
2 2

1

2
3 2
1 1
2
3 2
1 1

0

提示

样例 1 解释

有一行需要包含两名保镖，两行需要包含一名保镖；两列需要包含两名保镖，一种方案如下：

XX
X.
.X

其中 X 表示保镖，. 表示空位。

样例 2 解释

有两行必须全部是保镖，但是有一列却要仅有一名保镖，无法实现，故无解。

数据规模与约定

• 对于 $50\%$ 的数据，保证 $R,C\le 2000$，最多有 $10^6$ 名保镖；
• 对于 $100\%$ 的数据，保证保镖总数最多为 $10^{18}$，所有数字均为不超过 $10^9$ 的正整数，$1\le R,C\le 2\times 10^5$。

说明

题目译自 CEOI 2010 day 1 T3 bodyguards。

翻译版权为题目提供者