In linguistics and natural language processing, the meanings of different words can be compared by using a semantic feature table or vector.

The features chosen above are animal, pet, and quadruped, and the nouns chosen are dog, wolf, human, goldfish and rock. The different nouns have different values for each feature in their semantic vector, allowing words to be compared abstractly, even in languages that the researchers don't necessarily understand. Since these vectors can get very large and the titles of each feature doesn't necessarily matter in automated comparison, the vectors are given simply as a vector of integers without labels.

You are a researcher tasked with deciphering the language of an alien species, the Recursians. You have been provided with a corpus of words and their semantic vectors. There are also two words being focused on, and you would like to determine the degree of separation between these two words in the given corpus.

Two words are labelled as 'similar' if the Manhattan distance between their semantic vectors is not over a given threshold. The Manhattan distance is defined by the sum of the absolute differences of the values in each feature of the vectors. To determine the degree of separation between two words, we are looking for the smallest number of similar words that separates the two words.

Input

The first line contains an integer ~n\ (1 \leq n \leq 1000)~, detailing the amount of words in the corpus.

The second line contains an integer ~m\ (1 \leq m \leq 100)~, representing the dimension of each semantic vector (the number of elements/features).

The third line contains an integer ~t\ (1 \leq t \leq 10^5)~, representing the threshold. Only words with a Manhattan distance smaller than or equal to ~t~ are considered similar.

The next ~n~ lines each contain a word with a length between ~1~ and ~20~ consisting of only upper and lowercase English characters, followed by ~m~ space separated integers ~a_i\ (0 \leq a_i \leq 10^5)~ representing the values of each element in the semantic vector of that word.

The final line contains two words separated by a space. These are the words we are trying to find the minimum degree of separation between. These words are guaranteed to have appeared in the above lines.

Output

Output the minimum degree of separation between the two words as an integer. If there is no way to link the two words by only going between similar words, output ~-1~.

Example

Input 1

4
4
3
Blargh 3 5 1 1
Shlip 2 7 0 1
Plomp 1 5 1 0
Unkla 0 5 0 1
Unkla Blargh

Output 1

2

Explanation 1

Unkla is related only to Plomp, as their Manhattan distance is ~|0-1|+|5-5|+|0-1|+|1-0|=3~, while Unkla has a Manhattan distance of 4 with both Shlip and Blargh. Plomp has a Manhattan distance of 2 with Blargh, so they are related. Since Unkla is not directly related to Blargh, this is the smallest degree of separation (Unkla -> Plomp -> Blargh), so 2 is outputted.

Input 2

3
3
2
Blargh 10 10 10
Unkla 5 4 2
Argba 5 3 2
Argba Blargh

Output 2

-1

Explanation 2

While Argba is similar to Unkla, neither are similar to Blargh, so there is no way to get between Argba and Blargh with only similar words.