分数: 266 分
问题陈述
高桥正在组织一场跨越 N 学校文化节的日子。会场有 M 教室,每个教室每天只安排一堂课。课堂 j (1 \leq j \leq M)有一个 容量 of C_j 人。
当天 i (1 \leq i \leq N), K_i 游客前来参加文化节。每个访客指定 正好一个 剩余怪兽的 他们希望参加的课堂。让 P_{i,k} 表示所需的教室编号 k第访客(1 \leq k \leq K_i) 当天 i。请注意,多名访客可能希望在同一天进入同一间教室。
对于每一天,执行以下处理(每一天的处理是独立的,并且一天的结果不影响另一天)。统计当天每个教室的申请人数。如果一个教室的申请人数最多达到其容量(即申请人数 \leq 容量),那么所有申请者都可以参加该教室的讲座。另一方面,如果申请人数超过容量(即申请人数) > 容量),该教室的讲座是 已取消 出于安全原因,以及 无 希望参加该教室的 访客可以参加任何讲座。此外,想要参加的教室的讲座被取消的访客不会被重新分配到其他教室。
确定 访客总数 实际参加了所有讲座的人 N 活动天数(每天每个教室的参与者人数总和)。
约束
- 1 \leq N \leq 10^5
- 1 \leq M \leq 10^5
- 1 \leq C_j \leq 10^9 (1 \leq j \leq M)
- 1 \leq K_i (1 \leq i \leq N)
- \displaystyle \sum_{i=1}^{N} K_i \leq 2 \times 10^5
- 1 \leq P_{i,k} \leq M (1 \leq i \leq N,\ 1 \leq k \leq K_i)
- 所有输入值均为整数。
输入
N M
C_1 C_2 \ldots C_M
K_1
P_{1,1} P_{1,2} \ldots P_{1,K_1}
K_2
P_{2,1} P_{2,2} \ldots P_{2,K_2}
\vdots
K_N
P_{N,1} P_{N,2} \ldots P_{N,K_N}
- 第一行包含两个空格分隔的整数: N,事件的天数,以及 M,教室数量。
- 第二行包含空格分隔的整数 C_1, C_2, \ldots, C_M,代表每个教室的容量。
- 以下 2N 行提供每天的访客信息。当日信息 i 包括 2 行:
- 第一行包含一个整数 K_i, 当天访客数 i.
- 第二行包含空格分隔的整数 P_{i,1}, P_{i,2}, \ldots, P_{i,K_i},代表每个学生所需的教室编号 K_i 访客。
输出
在一行中输出所有实际参加讲座的访客总数 N 天。
示例输入 1
2 3 3 2 4 5 1 2 1 2 2 3 1 3 3
示例输出 1
5
示例输入 2
3 4 2 5 1 3 6 1 2 1 4 1 2 4 2 2 2 2 5 1 3 4 3 4
示例输出 2
10
示例输入 3
4 5 3 1 4 2 5 8 1 2 1 3 5 2 1 5 6 3 1 3 3 3 3 7 2 4 5 4 5 5 5 3 4 1 4
示例输出 3
17