← 返回题目列表

AtCoder · awc0077_e

E. 礼品分发

中文机器翻译题面 查看原题

分数: 466 分

问题陈述

高桥正在组织圣诞晚会。有 N 参加聚会,高桥决定给大家送一份礼物。

高桥已经准备好了 M 礼物类型。有 B_i 的礼物 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}
  • 第一行包含 N,参与者数量,以及 M,礼物类型的数量,以空格分隔。
  • 第二行包含 B_1, B_2, \ldots, B_M,每种类型的礼物数量,以空格分隔。
  • 以下 N 行描述了每个参与者的偏好。
  • 的 (2 + j)-第行包含类型数 K_j 认为 j- 第一个参与者的愿望,后跟类型编号 C_{j,1}, C_{j,2}, \ldots, C_{j,K_j},用空格分隔。如果 K_j = 0,没有给出类型编号,仅给出 写入 K_j 。

输出

在单行中输出满意的参与者的最大数量。


示例输入 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