K. K Common Interests
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Pinhão is a new social network that is becoming a craze on the internet. On it, users can interact, send messages, and share posts. The great thing about Pinhão is the formation of "pinhas": automatic groups of people who share common interests. A user can only view and share posts from the pinhas they participate in. In addition to this, when a user posts or shares something, that post becomes visible in all the pinhas they are part of.

Currently, the social network has $$$N$$$ active users. Each person's interest is represented by a string of $$$L$$$ characters. Two users belong to the same pinha if their level of common interest is greater than or equal to a value $$$K$$$. This level of interest is defined as the size of the largest common substring between the strings of interest of the two users.

For example: If user A has the string of interest "acabaa" and user B has "abcccc," the largest common substring between them is "ab." Therefore, the level of common interest is 2. If $$$K\leq2$$$, they will belong to the same cluster.

The administrators of Pinhão have hired you for a study. You will receive the values of $$$L$$$ and $$$K$$$, in addition to the strings of interest of all $$$N$$$ users. Your goal is to find out how many shares, at a minimum, are necessary for a publication by user 1 to be seen by user $$$N$$$.

Input

The first line of the input contains three integers, $$$N$$$ ($$$1 \le N \le 5 \times 10^{4}$$$), the number of users on the social network, $$$L$$$, the size of the strings of interest, and $$$K$$$ ($$$1 \le K \le L \le 20$$$), the minimum level of common interest for two users to participate in the same cluster. This is followed by $$$N$$$ lines, each containing a string consisting only of lowercase letters of size $$$L$$$, where line $$$i$$$ represents the interests of the $$$i$$$-th user.

Output

The output should be a single integer: the minimum number of shares required for a post by user 1 to be visible to user $$$N$$$, or -1 if this is not possible.

Examples
Input
3 4 2
abcd
abeb
zzeb
Output
1
Input
3 4 4
zzzz
aaaa
aaaa
Output
-1
Note

Explanation for example 1

Users 1 and 2 are part of one cluster, and users 2 and 3 are part of another cluster. Thus, a post by user 1 must be shared by user 2 to be visible to user 3.

Explanation for example 2

User 1 is isolated in their own cluster, so it is impossible for them to reach user $$$N$$$.