B - Classroom Assignment Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 266 点

問題文

高橋君は学校の文化祭で N 日間にわたるイベントを運営しています。会場には M 個の教室があり、各教室では毎日それぞれ 1 つの講演が行われる予定です。教室 j（1 \leq j \leq M）には 定員 C_j 人が設定されています。

i 日目（1 \leq i \leq N）には K_i 人の来場者が文化祭を訪れます。各来場者は参加したい教室を ちょうど 1 つ 指定します。i 日目の k 番目（1 \leq k \leq K_i）の来場者が希望する教室の番号を P_{i,k} とします。なお、同じ日に同じ教室を希望する来場者が複数いることもあります。

各日ごとに、以下の処理を行います（日ごとの処理は互いに独立であり、ある日の結果が別の日に影響することはありません）。教室ごとにその日の希望者数を集計し、ある教室の希望者数が定員以下（すなわち希望者数 \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}
  • 1 行目には、イベントの日数を表す整数 N と、教室の個数を表す整数 M が、スペース区切りで与えられる。
  • 2 行目には、各教室の定員を表す整数 C_1, C_2, \ldots, C_M が、スペース区切りで与えられる。
  • 続く 2N 行で、各日の来場者情報が与えられる。i 日目の情報は 2 行からなる。
  • 1 行目には、i 日目の来場者数を表す整数 K_i が与えられる。
  • 2 行目には、K_i 人の来場者がそれぞれ希望する教室の番号を表す整数 P_{i,1}, P_{i,2}, \ldots, P_{i,K_i} が、スペース区切りで与えられる。

出力

N 日間を通して実際に講演に参加できた来場者の延べ人数を 1 行で出力せよ。

入力例 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

Score : 266 pts

Problem Statement

Takahashi is organizing an event spanning N days at his school's cultural festival. The venue has M classrooms, and each classroom is scheduled to hold exactly one lecture per day. Classroom j (1 \leq j \leq M) has a capacity of C_j people.

On day i (1 \leq i \leq N), K_i visitors come to the cultural festival. Each visitor specifies exactly one classroom they wish to attend. Let P_{i,k} denote the classroom number desired by the k-th visitor (1 \leq k \leq K_i) on day i. Note that multiple visitors may wish to attend the same classroom on the same day.

For each day, the following process is performed (the processing for each day is independent, and the result of one day does not affect another day). The number of applicants for each classroom on that day is tallied. If the number of applicants for a classroom is at most its capacity (i.e., number of applicants \leq capacity), then all applicants can attend that classroom's lecture. On the other hand, if the number of applicants exceeds the capacity (i.e., number of applicants > capacity), the lecture in that classroom is canceled for safety reasons, and none of the visitors who wished to attend that classroom can participate in any lecture. Furthermore, visitors whose desired classroom's lecture was canceled are not reassigned to other classrooms.

Determine the total number of visitors who actually attended a lecture across all N days of the event (the sum of the number of participants in each classroom on each day).

Constraints

  • 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)
  • All input values are integers.

Input

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}
  • The first line contains two space-separated integers: N, the number of days of the event, and M, the number of classrooms.
  • The second line contains the space-separated integers C_1, C_2, \ldots, C_M, representing the capacity of each classroom.
  • The following 2N lines provide the visitor information for each day. The information for day i consists of 2 lines:
  • The first line contains an integer K_i, the number of visitors on day i.
  • The second line contains the space-separated integers P_{i,1}, P_{i,2}, \ldots, P_{i,K_i}, representing the classroom numbers desired by each of the K_i visitors.

Output

Output in a single line the total number of visitors who actually attended a lecture across all N days.

Sample Input 1

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

Sample Output 1

5

Sample Input 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

Sample Output 2

10

Sample Input 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

Sample Output 3

17