B - Logistyka

W państwie Maikuroubuge zdecydowano się na gwałtowną komputeryzację. Z tego powodu wybudowano w niektórych miastach fabryki procesorów. Jednak okazało się, żę wydatki na ich wybudowanie były większe niż przewidywano, zdrożał także transport. Postanowiono więc tak ustalić produkcję we wszystkich fabrykach, aby łączny koszt dostarczenia procesorów do miast które ich potrzebują był jak najmniejszy.

Wejście

W pierwszej linii znajduje się jedna liczba naturalna N określająca liczbę zestawów testowych.
Każdy zestaw zawiera: w pierszej linii trzy liczby naturalna M, F i K oznaczające odpowiednio liczbę miast, liczbę fabryk i liczbę dróg. (0 < M <= 5000; 0 < F <= M; 0 <= K <= 20000). W każdym z kolejnych F wierszy znajduje się jedna liczba naturalna A oznaczająca numer miasta w którym wybudowano fabrykę. (0 < A <= M). W każdym z kolejnych M wierszy znajduje się jedna liczba naturalna B oznaczająca liczbę procesorów potrzebnych w kolejnych miastach (poczynając od pierwszego). (0 <= B <= 100). W kolejnych K wierszach znajdują się dwie liczby naturalne C i D, oznaczające, że miasta o numerach C i D są połączone drogą. (0 < C,D <= M). Drogi są dwukierunkowe. Z każdego miasta można dojechać do każdego.

Wyjście

Należy dla każdego zestawu danych wypisać jedną liczbę w wierszu, będącą resztą z dzielenia przez 100000 minimalnego kosztu rozwiezienia procesorów. Przy czy koszt przewiezienia B procesorów z miasta C do D wynosi: B*ilość_przebytych_dróg.

Przykładowy test

Dla wejśćia:
2
3 1 3
2
2
3
5
1 2
3 1
3 2
4 1 5
3
2
4
1
5
1 3
3 4
2 4
4 1
1 2
Poprawną odpowiedzią jest:
7
15