A - Cooking Contest and Ingredients Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 266 点

問題文

高橋君は料理コンテストの審査員を務めています。このコンテストには N 人のシェフが参加し、それぞれのシェフには 1 から N までの番号が付けられています。

コンテストでは M 種類の食材が用いられ、食材には 1 から M までの番号が付けられています。シェフ i は C_i 種類の食材を得意としており、得意とする食材の番号は T_{i,1}, T_{i,2}, \ldots, T_{i,C_i} です。ただし C_i = 0 のとき、シェフ i は得意とする食材を持ちません。

コンテストの予選の結果、シェフ i は得点 V_i を獲得しました。N 人のシェフを以下の規則で順位付けし、1 位から K 位までの K 人が決勝に進出します。

  • 得点が高いシェフほど上位（順位の数値が小さい）とする。
  • 得点が同じシェフ同士では、シェフ番号が小さい方を上位とする。

この規則により、すべてのシェフの順位は一意に定まり、決勝に進出する 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}
  • 第 1 行には、シェフの人数 N、食材の種類数 M、決勝進出者数 K がスペース区切りで与えられる。
  • 続く N 行のうち i 行目（1 \leq i \leq N）には、まずシェフ i の得点 V_i と、シェフ i が得意とする食材の数 C_i がスペース区切りで与えられる。C_i \geq 1 の場合は、同じ行に続けて得意とする食材の番号 T_{i,1}, T_{i,2}, \ldots, T_{i,C_i} がスペース区切りで与えられる。C_i = 0 の場合は、その行には V_i と C_i の 2 つの値のみが記載される。

出力

決勝に進出した K 人全員が共通して得意とする食材の数を 1 行で出力せよ。

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

Score : 266 pts

Problem Statement

Takahashi is serving as a judge for a cooking contest. N chefs are participating in this contest, and each chef is assigned a number from 1 to N.

The contest uses M types of ingredients, numbered from 1 to M. Chef i specializes in C_i types of ingredients, and the numbers of the ingredients they specialize in are T_{i,1}, T_{i,2}, \ldots, T_{i,C_i}. When C_i = 0, chef i has no ingredients they specialize in.

As a result of the contest's preliminary round, chef i earned a score of V_i. The N chefs are ranked according to the following rules, and the top K chefs (ranked 1st through Kth) advance to the finals.

  • A chef with a higher score is ranked higher (i.e., has a smaller rank number).
  • Among chefs with the same score, the chef with the smaller chef number is ranked higher.

Under these rules, the ranking of all chefs is uniquely determined, and the K chefs who advance to the finals are also uniquely determined.

In the finals, the K advancing chefs will cook dishes using only ingredients that all of them commonly specialize in. That is, an ingredient can be used in the finals only if all K chefs who advanced to the finals specialize in that ingredient.

For Takahashi, find the number of ingredients that all K chefs advancing to the finals commonly specialize in. If there are no such ingredients, output 0.

Constraints

  • 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
  • For each chef i, T_{i,1}, T_{i,2}, \ldots, T_{i,C_i} are all distinct
  • All input values are integers

Input

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}
  • The first line contains the number of chefs N, the number of ingredient types M, and the number of finalists K, separated by spaces.
  • In the following N lines, the i-th line (1 \leq i \leq N) first contains chef i's score V_i and the number of ingredients C_i that chef i specializes in, separated by spaces. If C_i \geq 1, the ingredient numbers T_{i,1}, T_{i,2}, \ldots, T_{i,C_i} follow on the same line, separated by spaces. If C_i = 0, that line contains only the two values V_i and C_i.

Output

Output on a single line the number of ingredients that all K chefs advancing to the finals commonly specialize in.

Sample Input 1

3 5 2
100 3 1 2 3
80 4 1 2 4 5
90 2 1 2

Sample Output 1

2

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

Sample Output 2

2

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

Sample Output 3

3