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:
You are to help Mario choose the best path, along which he could get to the princess with minimum blood loss.
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.
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.
5 6 3
1 2 3
3 2 1
4 2 3
5 1 6
2 6 10