Air Bovinia verbindet die $N$ Farmen der Kühe, $1 \le N \le 20,000$. Wie jede Fluggesellschaft bestimmt sie $K$ Drehkreuze, $1 \le K \le 200,$ $K \le N$.

Es gibt $M$ Flüge in eine Richtung, $1 \le M \le 20,000$. Flug $i$ geht von $u_i$ nach $v_i$ für $d_i$ Dollar, $1 \le d_i \le 10{,}000$. Wie bei einer vernünftigen Gesellschaft ist mindestens ein Endpunkt ein Drehkreuz. Pro Farmpaar und Richtung gibt es höchstens einen Direktflug, keiner beginnt und endet auf derselben Farm.

Bessie leitet den Ticketdienst. Leider kamen während ihrer mehrstündigen Abwesenheit zum Kauen von köstlichem Heu $Q$ Anfragen für einfache Urlaubsreisen der Kühe, $1 \le Q \le 50,000$, Anfrage $i$ von $a_i$ nach $b_i$.

Hilf der überforderten Bessie, die Erfüllbarkeit jeder Anfrage und gegebenenfalls ihre minimalen Kosten zu bestimmen.

Um die Ausgabe zu verkürzen, gib nur die Gesamtzahl erfüllbarer Anfragen und deren minimale Gesamtkosten aus. Diese Zahl passt möglicherweise nicht in eine ganze Zahl mit $32$ Bit.

Eingabe

• Zeile $1$: ganze Zahlen $N$, $M$, $K$, $Q$.

• Zeilen $2..M+1$: Zeile $i+1$ enthält $u_i$, $v_i$, $d_i$; $1 \le u_i,v_i \le N$, $u_i \ne v_i$.

• Zeilen $M+2..M+K+1$: jeweils eine Drehkreuzkennung in $1..N$.

• Zeilen $M+K+2..M+K+Q+1$: zwei Zahlen für eine Anfrage von $a_i$ nach $b_i$; $1 \le a_i,b_i \le N$, $a_i \ne b_i$.

Ausgabe

• Zeile $1$: Anzahl erfüllbarer Anfragen.

• Zeile $2$: minimale Gesamtkosten ihrer Erfüllung.

Beispiele

Eingabe 1

3 3 1 2
1 2 10
2 3 10
2 1 5
2
1 3
3 1

Ausgabe 1

1
20

Hinweis

Für den ersten Flug ist nur $1 \to 2 \to 3$ möglich, Kosten $20$. Von Farm $3$ gehen keine Flüge ab; die armen Kühe sitzen fest.

Aufgabenautoren: Kalki Seksaria und Richard Peng