h2. Date de intrare

...

Pe prima linie a fisierului de intrare $amenzi.in$ se afla patru numere intregi {$N$}, {$M$}, {$K$} si {$P$} cu semnificatia din enunt. Urmatoarele $M$ linii contin cate trei numere {$a$}, $b$ si $c$ cu semnificatia ca exista o strada ce leaga intersectiile $a$ si $b$ si care poate fi parcursa in $c$ unitati de timp. Urmatoarele $K$ linii contin cate trei numere {$a$}, $b$ si $c$ cu semnificatia ca va avea loc o infractiune in intersectia {$a$}, la timpul $b$ si pentru care se va da o amenda in valoare de {$c$} unitati monetare. Apoi urmeaza $P$ linii cu cate doua numere $a$ si $b$ cu seminficatia ca este posibil ca Ion sa se intalneasca cu sotia sa in intersectia $a$ la momentul {$b$}.

h2. Date de iesire

...

In fisierul de iesire $amenzi.out$ vor exista $P$ linii coninand valoarea totala maxima pe care Ion o va obtine din amenzi in fiecare din cele $P$ cazuri descrise in fisierul de intrare.

h2. Restrictii
* Initial Ion se afla in intersectia $1$ la momentul {$0$}.

* ... ≤ ...

* Timpii la care se petrec infractiunile si la care Ion se poate intalni cu sotia sa sunt in intervalul [{$0, 1000$}]
* 0 ≤ K ≤ 1000
* 1 ≤ N ≤ 100
* 1 ≤ M ≤ 1000
* Costul unei amenzi va fi un intreg din intervalul [{$1, 1000$}]

h2. Exemplu