分数: 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