La Muntele Vrajit vin vara multi turisti. Sunt cabane la tot pasul. Ieri a fost o zi frumoasa, astfel încât nici un turist nu se afla în vreo cabana. Asa cum se mai întâmpla la munte, furtuna a venit din senin. Din acest moment, toti turistii au aleargat sa se adaposteasca în interiorul cabanelor.
Pentru simplitate, presupunem ca viteza de deplasare a oricarui turist este aceeasi, de un metru pe secunda. Turistii se deplaseaza numai pe carari. Acestea pot fi parcurse în ambele sensuri. Cararile nu se intersecteaza decât la capete. Cabanele, la fel ca si pozitiile initiale ale turistilor, sunt plasate în capetele unor carari. Fiecare cabana, poate adaposti un anumit numar maxim persoane. Turistii pot sa treaca prin pozitiile în care sunt amplasate cabane, fara sa consume timp, dar nu se pot adaposti decât daca în cabana respectiva mai este loc. Oricare carare poate fi parcursa în acelasi moment de timp de oricâti turisti.
Se stie ca exista m carari pe Muntele Vrajit. S-au etichetat cu numere naturale distincte, din intervalul [1,n], atât capetele celor m carari, cât si obiectivele izolate (neconectate prin carari). Fiecare carare este caracterizata de trei numere naturale: x y d, (x diferit de y), reprezentând etichetele celor doua capete si respectiv distanta exprimata în metri, dintre acestea.

Cerinta
Determinati cel mai scurt timp posibil Tmin necesar pentru ca toti turistii sa-si gaseasca adapost în cabane.

Date de intrare
Fisierul de intrare furtuna.in contine pe prima linie, despartite prin spatii, patru numere naturale: n, m, T si C, reprezentând numarul total de etichete utilizate, numarul de carari, numarul de turisti si respectiv numarul de cabane. Urmatoarele m linii, descriu cararile. Pe fiecare linie se gasesc cate trei numere x, y, d cu semnificatia din enunt. Pe linia m + 2, se gasesc T numere naturale, despartite prin spatii, reprezentând pozitiile initiale ale turistilor. Începând cu linia m + 3, urmeaza C linii, care descriu cabanele. Pe fiecare linie sunt câte doua numere naturale cab si nr, reprezentând pozitia în care este amplasata cabana, respectiv numarul maxim de turisti pe care îi poate adaposti.

Date de iesire
Fisierul de iesire furtuna.out va contine o singura linie pe care va fi scris numarul natural Tmin.

Restrictii si precizari
1 <= n <= 400
1 <= m <= 2000
1 <= T, C <= 100
1 <= d <= 300
Nu toate cararile sunt conectate între ele.
Pentru toate datele de test exista solutie.

Exemplu

prof. Constantin Galatan
C.N."Liviu Rebreanu" Bistrita-Nasaud
Contact:tucu_galatan@yahoo.com