分数: 266 分
问题陈述
高桥担任烹饪比赛的评委。 N 厨师正在参加本次比赛,每位厨师都被分配了一个编号, 1 to N.
比赛使用 M 成分类型,编号为 1 to M。厨师 i 专门从事 C_i 原料种类,以及其专攻的原料数量是 T_{i,1}, T_{i,2}, \ldots, T_{i,C_i}。当 C_i = 0,厨师 i 没有他们专门生产的成分。
比赛预赛结果,厨师 i 获得的分数为 V_i。的 N 厨师按照以下规则排名,排名靠前的 K 厨师(排名 1圣通 Kth) 晋级决赛。
- 得分较高的厨师排名较高(即排名数字较小)。
- 得分相同的厨师中,厨师编号较小的厨师排名较高。
在这些规则下,所有厨师的排名是唯一确定的,并且 K 晋级决赛的厨师也是独一无二的。
决赛中, K 晋级厨师将只使用他们共同擅长的食材来烹饪菜肴。也就是说,只有当所有食材都满足时才可以在决赛中使用某种食材。 K 晋级决赛的厨师专注于该食材。
对于高桥,找出所有成分的数量 K 晋级决赛的厨师普遍专攻。如果没有这种食材,则输出 0.
约束
- 1 \leq K \leq N \leq 10^5
- 1 \leq M \leq 10^5
- 0 \leq C_i \leq M
- \sum_{i=1}^{N} C_i \leq 2 \times 10^5
- 1 \leq V_i \leq 10^9
- 1 \leq T_{i,j} \leq M
- 对于每个厨师 i, T_{i,1}, T_{i,2}, \ldots, T_{i,C_i} 都是不同的
- 所有输入值均为整数
输入
N M K
V_1 C_1 T_{1,1} T_{1,2} \ldots T_{1,C_1}
V_2 C_2 T_{2,1} T_{2,2} \ldots T_{2,C_2}
\vdots
V_N C_N T_{N,1} T_{N,2} \ldots T_{N,C_N}
- 第一行包含厨师人数 N,成分类型数量 M,以及入围人数 K,用空格分隔。
- 在下面 N 行, i- 第行 (1 \leq i \leq N) 首先包含厨师 i的得分 V_i 和成分数量 C_i 那个厨师 i 专门从事,用空格分隔。如果 C_i \geq 1,成分编号 T_{i,1}, T_{i,2}, \ldots, T_{i,C_i} 位于同一行,以空格分隔。如果 C_i = 0,该行仅包含两个值 V_i 和 C_i.
输出
在一行上输出所有成分的数量 K 晋级决赛的厨师普遍擅长。
示例输入 1
3 5 2 100 3 1 2 3 80 4 1 2 4 5 90 2 1 2
示例输出 1
2
示例输入 2
5 6 3 50 2 1 3 100 3 1 2 3 100 4 1 2 3 4 75 3 2 3 5 60 0
示例输出 2
2
示例输入 3
10 8 4 500 5 1 2 3 4 5 450 4 1 2 3 6 480 6 1 2 3 4 5 6 300 3 1 2 7 520 4 1 2 3 8 200 2 1 2 490 5 1 2 3 5 7 350 4 2 3 4 5 400 3 1 3 4 100 1 1
示例输出 3
3