{"problem":{"name":"[SDCPC 2023] Building Company","description":{"content":"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,","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9557"},"statements":[{"statement_type":"Markdown","content":"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.\n\nThere 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.\n\nYou 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.\n\nNote that employees are not consumables. After undertaking a project the number of employees in your company won't decrease.\n\n## Input\n\nThere is only one test case in each test file.\n\nThe 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$.\n\nThe second line contains an integer $n$ ($1 \\le n \\le 10^5$) indicating the number of projects waiting to be undertaken.\n\nFor the following $2n$ lines, each two lines describe a project.\n\nThe $(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}$.\n\nThe $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}$.\n\nIt's guaranteed that neither the sum of $m_i$ nor the sum of $k_i$ will exceed $10^5$.\n\n## Output\n\nOutput one line containing one integer indicating the maximum number of projects you can undertake.\n\n[samples]\n\n## Note\n\nWe explain the sample test case as follows. Let $(t, u)$ indicate $u$ employees whose occupation is $t$.\n\nFirst, 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)\\}$.\n\nNext, 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)\\}$.\n\nNext, 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)\\}$.\n\nNext, 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)\\}$.\n\nAs the company does not have $3$ employees whose occupation is $2$, we cannot undertake the $3$-rd project.","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9557","tags":["模拟","2023","山东","O2优化","省赛/邀请赛"],"sample_group":[["2 2 1 1 2\n5\n1 3 1\n0\n2 1 1 2 1\n2 3 2 2 1\n3 1 5 2 3 3 4\n1 2 5\n3 2 1 1 1 3 4\n1 1 3\n0\n1 3 2","4"]],"created_at":"2026-03-03 11:09:25"}}