Problem

Super Mario is one of my favourite games in childhood. I remember, Mario is a brave plumber. To rescue the beautiful princess, he is always willing to take risks of fighting with monsters.

One day, trapped in a horrible castle, the princess is in trouble again. At that time, Mario is in a different castle and he decides to get to the princess' place at once. The way to save princess is full of dangers, for he has to pass several castles.

Although, there are K Monsters staying in each castle, the clever Mario notices that there is only one monster on duty for a period while the others are sleeping. To pass a castle, Mario only needs to beat the monster on duty.

Further, I should add some words to make things clear:

• There are N castles in total and M bidirectional roads between them
• Mario is in castle 1 and the princess is in castle N at time 0
• The time for Mario to go from one castle to a directly connected castle is always one unit, regardless of the distance between them
• The i-th monster in a castle will be on duty in the time period of [i-1, i), [K+i-1, K+i), [2*K+i-1, 2*K+i)...
• Mario always needs one unit of time to beat a monster and escapes from the castle before the next monster wakes up, but he may lost different amount of blood depending on the power of monster he meets
• After beating the monster on duty in castle N, the princess can be saved
• Mario can not stop, he must run or fight all the time until the task finished
• Mario will not enter a castle twice

You are to help Mario choose the best path, along which he could get to the princess with minimum blood loss.

Input

The first line constains an integer T indicating the number of test cases, then followed by T scenes. For each scene, three integers N, M, K will be given in the first line, where N is the number of castles, M is the number of roads, K is the number of monsters in a castle; then N lines follows, the i-th line describes monsters in the castle i with K integers, the j-th integer P of that line denotes the power of the j-th monster in castle i; finally M lines follows, each contains a pair of integers indicating a road between the two castles.

2 <= N <= 100, 1 <= K <= 100, 1 <= P <= 100.

Output

For each scene, print the minimum blood loss to get to the princess in a single line. If there is no way to get there, print "-1" instead.

Sample Input

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

Sample Output

5

Author: wiltord