Air Bovinia relie $N$ fermes où vivent les vaches ($1 \le N \le 200$). Comme toute compagnie, elle choisit $K$ hubs ($1 \le K \le 100,$ $K \le N$). Les fermes sont numérotées $1..N$, les hubs $1..K$.

Il existe $M$ vols à sens unique ($1 \le M \le 10,000$). Le vol $i$ va de $u_i$ à $v_i$ et coûte $d_i$ dollars ($1 \le d_i \le 1,000,000$).

Elle reçoit $Q$ demandes de voyages aller simple ($1 \le Q \le 10,000$), la $i$-ième de $a_i$ à $b_i$. De $a_i$ à $b_i$, toute suite de vols directs est permise, même en revisitant des fermes, mais au moins un hub doit être inclus ; il peut être le départ, l'arrivée ou une ferme intermédiaire. Ainsi, de $a_i$ à $b_i$, aucun trajet valide n'existe parfois. Pour les autres demandes, trouvez le coût minimal d'un trajet valide.

Entrée

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

• Lignes $2..1+M$ : la ligne $i+1$ contient $u_i$, $v_i$, $d_i$ pour le vol $i$.

• Lignes $2+M..1+M+Q$ : la ligne $1+M+i$ décrit le voyage $i$ par $a_i$ et $b_i$.

Sortie

• Ligne $1$ : nombre de demandes, parmi $Q$, admettant un trajet valide.

• Ligne $2$ : somme des coûts minimaux pour toutes les demandes admettant un trajet valide.

Exemples

Entrée 1

3 3 1 3
3 1 10
1 3 10
1 2 7
3 2
2 3
1 2

Sortie 1

2
24

Remarque

Il y a $3$ fermes, numérotées $1\ldots3$ ; $1$ est un hub. Le vol de $3$ à $1$ coûte $10$, etc. Demandes : $3\to2$, $2\to3$, $1\to2$.

$3\to2$ a un seul trajet de coût $10+7$. Aucun pour $2\to3$, car aucun vol ne quitte $2$. $1\to2$ a un seul trajet valide de coût $7$.

Auteur du problème : Kalki Seksaria