3985. 雨和卡布奇诺

【题目描述】

你在经营一家咖啡店，初始时出售 $n$ 种咖啡。第 $i$ 种咖啡的品种为 $t_i$，你拥有 $u_i$ 台对应的咖啡机。

现在共有 $m$ 名赞助商要来考察。对于第 $i$ 名赞助商，他对你的咖啡店提出了 $l_i$ 项要求。第 $j$ 项要求为，你必须拥有至少 $b_{i,j}$ 台 $a_{i,j}$ 品种的咖啡机。如果你满足了他的全部要求，他就会赞助你一些新的咖啡机，分为 $k_i$ 种，第 $j$ 种为 $c_{i,j}$ 品种的咖啡机，共 $d_{i,j}$ 台。

你可以按任意顺序接待任意名赞助商，每名赞助商至多赞助一次。请问你最多能获得多少次赞助。

【输入格式】

第一行首先一个正整数 $n$。接下来 $2n$ 个数，依次表示 $t_1,u_1,t_2,u_2,...,t_n,u_n$。保证对于 $i\neq j$，有 $t_i \neq t_j$。

第二行一个正整数 $m$。

接下来 $2m$ 行，每两行描述一名赞助商。对于第 $i$ 名赞助商：

第一行首先一个正整数 $l_i$。接下来 $2l_i$ 个数，依次表示 $a_{i,1},b_{i,1},a_{i,2},b_{i,2},...,a_{i,l_i},b_{i,l_i}$。保证对于 $j\neq k$，有 $a_{i,j} \neq a_{i,k}$。

第二行首先一个正整数 $k_i$。接下来 $2k_i$ 个数，依次表示 $c_{i,1},d_{i,1},c_{i,2},d_{i,2},...,c_{i,k_i},d_{i,k_i}$。保证对于 $j\neq k$，有 $c_{i,j} \neq c_{i,k}$。

【输出格式】

一个整数，表示你最多能获得多少次赞助。

【样例输入】

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

【样例说明】

依次接待第 $5,1,2,4$ 名赞助商，共获得 $4$ 次赞助。

【数据规模与约定】

大样例

对于 $100\%$ 的数据 $1 \le n,m,\sum{l_i},\sum{k_i} \le 10^5, 1\le u_i,t_i,a_{i,j},b_{i,j},c_{i,j},d_{i,j}\le 10^9$。

·$Subtask1(40pts): n,m\le 500$。

·$Subtask2(20pts): n,m\le 5000$。

·$Subtask3(40pts): 无特殊限制$。

【来源】

[SDCPC2023] Building Company。