Air Bovinia relie les $N$ fermes des vaches, $1 \le N \le 20,000$. Comme toute compagnie, elle désigne $K$ plateformes de correspondance, $1 \le K \le 200,$ $K \le N$.

Elle propose $M$ vols à sens unique, $1 \le M \le 20,000$. Le vol $i$ va de $u_i$ à $v_i$ pour $d_i$ dollars, $1 \le d_i \le 10{,}000$. Comme toute compagnie raisonnable, au moins une extrémité est une plateforme. Au plus un vol direct existe par paire dans chaque direction, et aucun ne revient à sa ferme de départ.

Bessie gère la billetterie. Malheureusement, pendant qu’elle s’absentait quelques heures pour mâcher du foin délicieux, $Q$ demandes de voyages de vacances des vaches à sens unique arrivent, $1 \le Q \le 50,000$. La demande $i$ va de $a_i$ à $b_i$.

Aidez Bessie, débordée, à déterminer si chaque demande est réalisable et son coût minimal dans ce cas.

Pour réduire la sortie, affichez seulement le nombre total de demandes réalisables et leur coût total minimal. Ce nombre peut dépasser un entier de $32$ bits.

Entrée

• Ligne $1$ : entiers $N$, $M$, $K$, $Q$.

• Lignes $2..M+1$ : la ligne $i+1$ contient $u_i$, $v_i$, $d_i$ ; $1 \le u_i,v_i \le N$, $u_i \ne v_i$.

• Lignes $M+2..M+K+1$ : un identifiant de plateforme dans $1..N$ par ligne.

• Lignes $M+K+2..M+K+Q+1$ : deux nombres pour une demande de $a_i$ à $b_i$ ; $1 \le a_i,b_i \le N$, $a_i \ne b_i$.

Sortie

• Ligne $1$ : nombre de demandes réalisables.

• Ligne $2$ : coût total minimal pour les réaliser.

Exemples

Entrée 1

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

Sortie 1

1
20

Remarque

Pour le premier vol, seul $1 \to 2 \to 3$ est possible, coût $20$. Aucun vol ne part de la ferme $3$ : les pauvres vaches y sont bloquées.

Auteurs du problème : Kalki Seksaria et Richard Peng