Keyboard and Virus

Kolya thinks he is a very cool programmer. He is also a hipster, so he refuses to type on an ordinary keyboard with rubber under the keys. Instead he bought a trendy vintage mechanical keyboard with real springs under each key. The keyboard is so old that every symbol printed on its keys has worn off, but Kolya is not bothered, because he is a very cool programmer.

Kolya types in $n$ different languages on this keyboard. Conveniently, each language has exactly $m$ letters, which equals the number of keys on his keyboard. Every symbol of every language is in the encoding Kolya uses, so each symbol is a number from $1$ to $c$. A symbol may appear in any number of languages, but for any two different languages there is at least one symbol that is in one of them and missing from the other. Some numbers from $1$ to $c$ may not correspond to any symbol Kolya knows.

Kolya's friends are tired of him carrying this keyboard everywhere and annoying people with its loud clicks. They wrote a computer virus that does two nasty things every time the language is switched:

• Instead of switching to a specific language, it switches to a language chosen at random from the $n$ languages Kolya uses (the language may stay the same).
• The keyboard layout for that language is shuffled in an arbitrary way, with only one condition: different keys get different symbols.

When the virus hits, Kolya panics at first, but soon realizes things are not so bad. By pressing each key once, he can find which symbol each key produces, and from that information he can determine the active language. However, he thinks the current language can be determined with fewer key presses. Help Kolya show his friends that he really is a cool programmer by computing the minimum number of key presses he needs in the worst case to determine the current language.

The first line contains two integers $n$ and $m$: the number of languages Kolya uses and the number of keys on his new keyboard (which is also the number of letters in every language).

The next $n$ lines describe the languages. Each line contains $m$ symbol numbers in Kolya's encoding. The numbers are given in arbitrary order. All numbers are integers from $1$ to $c$. The value $c$ is not given in the input, but it is fixed for each test group.

It is guaranteed that $n$, $m$, and $c$ are positive.

Print one integer: the minimum number of keys Kolya must press to determine the current language in the worst case.

In the first test from the statement, if Kolya is unlucky and presses the keys corresponding to $1$ and $3$, he cannot tell which language he is typing in.