P9557 [SDCPC 2023] Building Company

您是一家建筑公司的老板。一开始，公司共有 $g$ 类员工，每一类员工都属于一个工种。第 $i$ 类员工的工种编号为 $t_i$，共有 $u_i$ 人。 市场上共有 $n$ 项工程等待承接。想要承接第 $i$ 项工程，您的公司需要满足 $m_i$ 项要求，其中第 $j$ 项要求您的公司至少有工种编号为 $a_{i, j}$ 的员工 $b_{i, j}$ 人。承接该工程后，您的公司将会更加有名，并吸引 $k_i$ 类员工加入公司，其中第 $j$ 类员工的工种编号为 $c_{i, j}$，共有 $d_{i, j}$ 人。 您可以按任意顺序承接任意数量的工程，每项工程最多只能被承接一次。求最多能承接多少工程。 请注意：员工不是消耗品。承接一项工程后，员工的数量不会减少。

每个测试文件仅有一组测试数据。 第一行首先输入一个整数 $g$（$1 \le g \le 10^5$）表示一开始公司内员工的种类数。接下来输入 $g$ 对整数 $t_1, u_1, t_2, u_2, \cdots t_g, u_g$（$1 \le t_i, u_i \le 10^9$），其中 $t_i$ 和 $u_i$ 表示一开始工种编号为 $t_i$ 的员工共有 $u_i$ 人。保证对于所有 $1 \le i < j \le g$ 有 $t_i \ne t_j$。 第二行输入一个整数 $n$（$1 \le n \le 10^5$）表示等待承接的工程数量。 对于接下来 $2n$ 行，每两行描述一项工程。 第 $(2i - 1)$ 行首先输入一个整数 $m_i$（$0 \le m_i \le 10^5$）表示承接第 $i$ 项工程有几项要求。接下来输入 $m_i$ 对整数 $a_{i, 1}, b_{i, 1}, a_{i, 2}, b_{i, 2}, \cdots, a_{i, m_i}, b_{i, m_i}$（$1 \le a_{i, j}, b_{i, j} \le 10^9$），其中 $a_{i, j}$ 和 $b_{i, j}$ 表示公司至少要有工种编号为 $a_{i, j}$ 的员工 $b_{i, j}$ 人。保证对于所有 $1 \le x < y \le m_i$ 有 $a_{i, x} \ne a_{i, y}$。 第 $2i$ 行首先输入一个整数 $k_i$（$0 \le k_i \le 10^5$）表示承接第 $i$ 项工程之后有几类员工加入公司。接下来输入 $k_i$ 对整数 $c_{i, 1}, d_{i, 1}, c_{i, 2}, d_{i, 2}, \cdots, c_{i, k_i}, d_{i, k_i}$（$1 \le c_{i, j}, d_{i, j} \le 10^9$），其中 $c_{i, j}$ 和 $d_{i, j}$ 表示工种编号为 $c_{i, j}$ 的员工共 $d_{i, j}$ 人加入公司。保证对于所有 $1 \le x < y \le k_i$ 有 $c_{i, x} \ne c_{i, y}$。 保证 $m_i$ 与 $k_i$ 之和均不超过 $10^5$。

输出一行一个整数表示最多能承接几项工程。 **【样例解释】** 样例解释如下，用 $(t, u)$ 表示工种为 $t$ 的员工有 $u$ 名。 首先承接没有任何要求的第 $5$ 项工程，承接后工种为 $3$ 的 $2$ 名员工加入公司。公司内现有员工为 $\{(1, 2), (2, 1), (3, 2)\}$。 接下来承接第 $1$ 项工程，承接后没有员工加入公司。公司内现有员工仍为 $\{(1, 2), (2, 1), (3, 2)\}$。 接下来承接第 $2$ 项工程，承接后工种为 $3$ 的 $2$ 名员工，以及工种为 $2$ 的 $1$ 名员工加入公司。公司内现有员工为 $\{(1, 2), (2, 2), (3, 4)\}$。 接下来承接第 $4$ 项工程，承接后工种为 $1$ 的 $3$ 名员工加入公司。公司内现有员工为 $\{(1, 5), (2, 2), (3, 4)\}$。 由于工种为 $2$ 的员工不足 $3$ 名，因此无法承接仅剩的第 $3$ 项工程。

We explain the sample test case as follows. Let $(t, u)$ indicate $u$ employees whose occupation is $t$. First, undertake the $5$-th project with no requirements. After undertaking the project, there are $2$ employees, whose occupation is $3$, joining the company. The company now have these employees: $\{(1, 2), (2, 1), (3, 2)\}$. Next, undertake the $1$-st project. After undertaking the project, no employee joins the company. The company now still have these employees: $\{(1, 2), (2, 1), (3, 2)\}$. Next, undertake the $2$-nd project. After undertaking the project, there are $2$ employees, whose occupation is $3$, and $1$ employee, whose occupation is $2$, joining the company. The company now have these employees: $\{(1, 2), (2, 2), (3, 4)\}$. Next, undertake the $4$-th project. After undertaking the project, there are $3$ employees, whose occupation is $1$, joining the company. The company now have these employees: $\{(1, 5), (2, 2), (3, 4)\}$. As the company does not have $3$ employees whose occupation is $2$, we cannot undertake the $3$-rd project.