Amazon

"If you think it’s simple, then you have misunderstood the problem" (Bjarne Stroustrup)

Jeffrey dorește să își extindă magazinul său online și în România. Pentru a asigura obsesia pentru satisfacția clienților, el stabilește o strategie de livrare a comenzilor eficientă, automată, și într-un timp cât mai scurt.

România este formată din $N$ orașe conectate între ele, existând un traseu unic între oricare două orașe. Un traseu este o secvență de drumuri care conectează două orașe, astfel încât niciun drum nu se repetă. În total, există $N - 1$ drumuri bidirecționale care conectează orașele.

Fiecare drum are și un cost asociat. Echipa lui Jeffrey a creat o listă de $M$ perechi de orașe între care se va circula foarte des pentru livrarea coletelor. Definim costul unei perechi de orașe $(x, y)$ ca fiind suma costurilor drumurilor din traseul de la orașul $x$ la orașul $y$. De asemenea, definim costul total ca fiind suma tuturor costurilor celor $M$ perechi de orașe date.

Jeffrey poate să aplice următorul tip de operație: selectează un drum cu un cost strict pozitiv și îi scade costul cu $1$. Din motive de "frugality", această operație poate fi aplicată de cel mult $K$ ori, unde $K$ este un număr natural.

Cerință

Se cere să găsiți costul total minim ce poate fi obținut, după aplicarea de cel mult $K$ ori a operației menționate mai sus.

Date de intrare

Pe prima linie a fișierului de intrare se află un număr natural $N$, reprezentând numărul de orașe.

Pe următoarele $N - 1$ linii se află câte $3$ numere $x$, $y$ și $w$, reprezentând faptul că există un drum bidirecțional între orașele $x$ și $y$, cu costul egal cu $w$. Orașele sunt numerotate de la $0$ la $N - 1$.

Pe următoarea linie se află numerele $M$ și $K$, reprezentând numărul de perechi de orașe, respectiv numărul de operații ce pot fi aplicate, urmând apoi $M$ linii care conțin fiecare câte două numere $x$ și $y$ reprezentând cele $M$ perechi de orașe.

Date de ieșire

Pe prima linie a fișierului de ieșire se va afla un singur număr, reprezentând costul total minim ce va putea fi obținut, modulo $666 \ 013$.

Restricții și precizări

• $1 \leq N \leq 200 \ 000$
• $0 \leq K \leq 200 \ 000$
• $1 \leq M \leq N$
• $1 \leq w \leq 20$
• $0 \leq x, y < N$, $x \neq y$
• Operația de scădere a costului unui drum poate fi aplicată de mai multe ori pentru același drum, atât timp cât costul drumului nu devine un număr negativ.
• Pentru teste în valoare de $20$ de puncte se garantează că $1 \leq N,K \leq 1 \ 000$.
• Pentru alte teste în valoare de $30$ de puncte se garantează că $K = 0$.
• Pentru restul testelor în valoare de $50$ de puncte nu există restricții suplimentare.

Exemplu

amazon.in

5
1 0 4
0 2 3
1 3 4
1 4 4
3 5
2 4
1 4
3 4

amazon.out

10

Explicație

Putem alege să aplicăm operația de scădere a costului drumului pe drumul de la orașul $1$ la orașul $4$ de $4$ ori. Astfel, costul drumului va deveni $0$.

Mai putem aplica încă o dată operația pentru drumul de la orașul $1$ la $3$, micșorând costul acestuia la $3$. Costul traseului între orașele $2$ și $4$ va fi suma costurilor drumurilor $2 \rightarrow 0$, $0 \rightarrow 1$ și $1 \rightarrow 4$, adică $3 + 4 + 0 = 7$. Costul traseului între orașele $1$ și $4$ va fi costul drumului $1 \rightarrow 4$, adică $0$. Costul traseului între orașele $3$ și $4$ va fi suma costurilor drumurilor $3 \rightarrow 1$ și $1 \rightarrow 4$, adică $3 + 0 = 3$.

Astfel, costul total este $7 + 0 + 3 = 10$.