E - Gift Distribution Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 466 点

問題文

高橋君はクリスマスパーティーの幹事をしています。パーティーには N 人の参加者がおり、高橋君は全員にプレゼントを配ることにしました。

高橋君は M 種類のプレゼントを用意しました。i 番目の種類のプレゼントは B_i 個あります。すべての参加者にちょうど 1 個ずつプレゼントを渡す必要がありますが、各種類のプレゼントは用意した個数を超えて配ることはできません。プレゼントの総数（B_1 + B_2 + \cdots + B_M）は N 以上であることが保証されているため、全員に配ることは必ず可能です。

参加者にはそれぞれ欲しいものの希望があります。j 番目の参加者は K_j 種類のプレゼントを希望しており、そのいずれかを受け取ると満足します。希望するプレゼントの種類の番号は C_{j,1}, C_{j,2}, \ldots, C_{j,K_j} として与えられます。K_j = 0 の場合、その参加者はどのプレゼントを受け取っても満足しません。希望していない種類のプレゼントを渡すことも許されますが、その参加者は満足しません。

高橋君は、満足する参加者の人数を最大化するようにプレゼントを配りたいと考えています。満足する参加者の人数の最大値を求めてください。

制約

  • 1 \leq N \leq 500
  • 1 \leq M \leq 500
  • 1 \leq B_i \leq N（1 \leq i \leq M）
  • B_1 + B_2 + \cdots + B_M \geq N
  • 0 \leq K_j \leq M（1 \leq j \leq N）
  • 1 \leq C_{j,k} \leq M（1 \leq j \leq N, 1 \leq k \leq K_j）
  • j 番目の参加者について、C_{j,1}, C_{j,2}, \ldots, C_{j,K_j} はすべて異なる
  • 入力はすべて整数である

入力

N M
B_1 B_2 \cdots B_M
K_1 C_{1,1} C_{1,2} \cdots C_{1,K_1}
K_2 C_{2,1} C_{2,2} \cdots C_{2,K_2}
:
K_N C_{N,1} C_{N,2} \cdots C_{N,K_N}
  • 1 行目には、参加者の人数を表す N と、プレゼントの種類数を表す M が、スペース区切りで与えられる。
  • 2 行目には、各種類のプレゼントの個数を表す B_1, B_2, \ldots, B_M が、スペース区切りで与えられる。
  • 3 行目から N 行分にわたって、各参加者の希望が与えられる。
  • 2 + j 行目では、j 番目の参加者が希望するプレゼントの種類数 K_j と、その種類の番号 C_{j,1}, C_{j,2}, \ldots, C_{j,K_j} が、スペース区切りで与えられる。K_j = 0 の場合、種類の番号は与えられず、K_j のみが記載される。

出力

満足する参加者の人数の最大値を 1 行で出力してください。

入力例 1

3 2
2 2
1 1
1 1
1 2

出力例 1

3

入力例 2

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

出力例 2

1

入力例 3

6 3
2 2 3
1 1
1 1
2 1 2
1 2
1 3
0

出力例 3

5

入力例 4

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

出力例 4

9

入力例 5

1 1
1
0

出力例 5

0

Score : 466 pts

Problem Statement

Takahashi is organizing a Christmas party. There are N participants at the party, and Takahashi has decided to give a present to everyone.

Takahashi has prepared M types of presents. There are B_i presents of the i-th type. He must give exactly 1 present to each participant, but he cannot distribute more presents of each type than the number he has prepared. It is guaranteed that the total number of presents (B_1 + B_2 + \cdots + B_M) is at least N, so it is always possible to give a present to everyone.

Each participant has their own preferences. The j-th participant desires K_j types of presents, and will be satisfied if they receive any one of them. The type numbers of the desired presents are given as C_{j,1}, C_{j,2}, \ldots, C_{j,K_j}. If K_j = 0, that participant will not be satisfied no matter which present they receive. It is allowed to give a participant a present of a type they do not desire, but that participant will not be satisfied.

Takahashi wants to distribute the presents so as to maximize the number of satisfied participants. Find the maximum number of satisfied participants.

Constraints

  • 1 \leq N \leq 500
  • 1 \leq M \leq 500
  • 1 \leq B_i \leq N (1 \leq i \leq M)
  • B_1 + B_2 + \cdots + B_M \geq N
  • 0 \leq K_j \leq M (1 \leq j \leq N)
  • 1 \leq C_{j,k} \leq M (1 \leq j \leq N, 1 \leq k \leq K_j)
  • For the j-th participant, C_{j,1}, C_{j,2}, \ldots, C_{j,K_j} are all distinct
  • All input values are integers

Input

N M
B_1 B_2 \cdots B_M
K_1 C_{1,1} C_{1,2} \cdots C_{1,K_1}
K_2 C_{2,1} C_{2,2} \cdots C_{2,K_2}
:
K_N C_{N,1} C_{N,2} \cdots C_{N,K_N}
  • The first line contains N, the number of participants, and M, the number of types of presents, separated by a space.
  • The second line contains B_1, B_2, \ldots, B_M, the number of presents of each type, separated by spaces.
  • The following N lines describe each participant's preferences.
  • The (2 + j)-th line contains the number of types K_j that the j-th participant desires, followed by the type numbers C_{j,1}, C_{j,2}, \ldots, C_{j,K_j}, separated by spaces. If K_j = 0, no type numbers are given, and only K_j is written.

Output

Output the maximum number of satisfied participants in a single line.

Sample Input 1

3 2
2 2
1 1
1 1
1 2

Sample Output 1

3

Sample Input 2

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

Sample Output 2

1

Sample Input 3

6 3
2 2 3
1 1
1 1
2 1 2
1 2
1 3
0

Sample Output 3

5

Sample Input 4

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

Sample Output 4

9

Sample Input 5

1 1
1
0

Sample Output 5

0