题目描述

You're the boss of a building company. At the beginning, there are $g$ types of employees in the company, and different types of employees have different occupations. For the $i$-th type of employees, their occupation can be numbered as $t_i$ and there are $u_i$ employees in total.

There are $n$ building projects in the market waiting to be undertaken. To undertake the $i$-th project, your company must meet $m_i$ requirements. The $j$-th requirement requires that your company has at least $b_{i, j}$ employees whose occupation is $a_{i, j}$. After undertaking the project, your company will become more famous and will attract $k_i$ types of employees to join your company. The occupation of the $j$-th type of employees is $c_{i, j}$ and there are $d_{i, j}$ employees in total.

You can undertake any number of projects in any order. Each project can be undertaken at most once. Calculate the maximum number of projects you can undertake.

Note that employees are not consumables. After undertaking a project the number of employees in your company won't decrease.

输入格式

There is only one test case in each test file.

The first line of the input first contains an integer $g$ ($1 \le g \le 10^5$) indicating the number of types of employees in the company at the beginning. Then $g$ pairs of integers $t_1, u_1, t_2, u_2, \cdots t_g, u_g$ follow ($1 \le t_i, u_i \le 10^9$), where $t_i$ and $u_i$ indicate that there are $u_i$ employees whose occupation is $t_i$. It's guaranteed that for all $1 \le i < j \le g$ we have $t_i \ne t_j$.

The second line contains an integer $n$ ($1 \le n \le 10^5$) indicating the number of projects waiting to be undertaken.

For the following $2n$ lines, each two lines describe a project.

The $(2i - 1)$-th line first contains an integer $m_i$ ($0 \le m_i \le 10^5$) indicating the number of requirements to undertake the $i$-th project. Then $m_i$ pairs of integers $a_{i, 1}, b_{i, 1}, a_{i, 2}, b_{i, 2}, \cdots, a_{i, m_i}, b_{i, m_i}$ follow ($1 \le a_{i, j}, b_{i, j} \le 10^9$) where $a_{i, j}$ and $b_{i, j}$ indicate that the company is required to have at least $b_{i, j}$ employees whose occupation is $a_{i, j}$. It's guaranteed that for all $1 \le x < y \le m_i$ we have $a_{i, x} \ne a_{i, y}$.

The $2i$-th line first contains an integer $k_i$ ($0 \le k_i \le 10^5$) indicating the number of types of employees to join the company after undertaking the $i$-th project. Then $k_i$ pairs of integers $c_{i, 1}, d_{i, 1}, c_{i, 2}, d_{i, 2}, \cdots, c_{i, k_i}, d_{i, k_i}$ follow ($1 \le c_{i, j}, d_{i, j} \le 10^9$) where $c_{i, j}$ and $d_{i, j}$ indicate that there are $d_{i, j}$ employees whose occupation is $c_{i, j}$ joining the company. It's guaranteed that for all $1 \le x < y \le k_i$ we have $c_{i, x} \ne c_{i, y}$.

It's guaranteed that neither the sum of $m_i$ nor the sum of $k_i$ will exceed $10^5$.

输出格式

Output one line containing one integer indicating the maximum number of projects you can undertake.

题目大意

【题目描述】

您是一家建筑公司的老板。一开始，公司共有 $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$ 项工程。

2 2 1 1 2
5
1 3 1
0
2 1 1 2 1
2 3 2 2 1
3 1 5 2 3 3 4
1 2 5
3 2 1 1 1 3 4
1 1 3
0
1 3 2

4

提示

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.