Air Bovinia collega le $N$ fattorie delle mucche, $1 \le N \le 20,000$. Come ogni compagnia, designa $K$ scali centrali, $1 \le K \le 200,$ $K \le N$.

Offre $M$ voli di sola andata, $1 \le M \le 20,000$. Il volo $i$ va da $u_i$ a $v_i$ per $d_i$ dollari, $1 \le d_i \le 10{,}000$. Come una compagnia sensata, almeno un estremo è scalo centrale. Al massimo un volo diretto per coppia e direzione, nessuno con stessa partenza e arrivo.

Bessie gestisce i biglietti. Purtroppo, mentre era fuori per ore a masticare fieno delizioso, sono arrivate $Q$ richieste di viaggi di vacanza delle mucche di sola andata, $1 \le Q \le 50,000$, la $i$ da $a_i$ a $b_i$.

Aiuta Bessie, sommersa, a verificare ogni richiesta e il costo minimo se fattibile.

Per ridurre l'output, stampa solo il totale delle richieste fattibili e il loro costo totale minimo. Questo numero può non entrare in un intero di $32$ bit.

Input

• Riga $1$: interi $N$, $M$, $K$, $Q$.

• Righe $2..M+1$: la riga $i+1$ contiene $u_i$, $v_i$, $d_i$; $1 \le u_i,v_i \le N$, $u_i \ne v_i$.

• Righe $M+2..M+K+1$: un identificatore di scalo in $1..N$ per riga.

• Righe $M+K+2..M+K+Q+1$: due numeri per richiesta da $a_i$ a $b_i$; $1 \le a_i,b_i \le N$, $a_i \ne b_i$.

Output

• Riga $1$: numero di richieste fattibili.

• Riga $2$: costo totale minimo per soddisfarle.

Esempi

Input 1

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

Output 1

1
20

Nota

Per il primo volo solo $1 \to 2 \to 3$ è fattibile, costo $20$. Nessun volo lascia la fattoria $3$, così le povere mucche sono bloccate lì.

Autori del problema: Kalki Seksaria e Richard Peng