Description

The owner of the candy shop sells a total of $M$ flavors of candy. For convenience, we number the $M$ flavors from $1$ to $M$.

Xiaoming wants to taste candies of all flavors. Unfortunately, the owner does not sell candies individually, but only sells them in whole packs, with $K$ candies per pack.

Luckily, each candy pack lists the flavors of the $K$ candies inside, so Xiaoming can know the flavors in a pack before buying it.

Given $N$ packs of candy, please compute the minimum number of packs Xiaoming needs to buy in order to taste all flavors of candy.

Input Format

The first line contains three integers $N$, $M$, and $K$.

In the next $N$ lines, each line contains $K$ integers $T_1, T_2, \cdots , T_K$, representing the flavors of one pack of candy.

Output Format

Output one integer as the answer. If Xiaoming cannot taste all flavors, output $-1$.

6 5 3
1 1 2
1 2 3
1 1 3
2 3 5
5 4 2
5 1 2

2

Hint

For $30\%$ of the testdata, $1 \le N \le 20$.

For all testdata, $1 \le N \le 100$, $1 \le M \le 20$, $1 \le K \le 20$, $1 \le T_i \le M$.

Lanqiao Cup 2019 Provincial Contest A Division, Problem I.

Translated by ChatGPT 5