Air Bovinia conecta las $N$ granjas de las vacas, $1 \le N \le 20,000$. Como cualquier aerolínea, designa $K$ centros de conexión, $1 \le K \le 200,$ $K \le N$.

Ofrece $M$ vuelos de ida, $1 \le M \le 20,000$. El vuelo $i$ va de $u_i$ a $v_i$ por $d_i$ dólares, $1 \le d_i \le 10{,}000$. Como una aerolínea sensata, al menos un extremo es centro. Hay como máximo un vuelo directo por par en cada dirección, y ninguno empieza y termina en la misma granja.

Bessie gestiona billetes. Por desgracia, mientras se ausentó unas horas a masticar heno delicioso, recibió $Q$ peticiones de viajes de vacaciones de ida de las vacas, $1 \le Q \le 50,000$, la $i$ de $a_i$ a $b_i$.

Ayuda a Bessie, abrumada, a decidir si cada petición es posible y su coste mínimo si lo es.

Para reducir la salida, imprime solo el total de peticiones posibles y su coste total mínimo. Este número puede no caber en entero de $32$ bits.

Entrada

• Línea $1$: enteros $N$, $M$, $K$, $Q$.

• Líneas $2..M+1$: la línea $i+1$ contiene $u_i$, $v_i$, $d_i$; $1 \le u_i,v_i \le N$, $u_i \ne v_i$.

• Líneas $M+2..M+K+1$: un identificador de centro en $1..N$ por línea.

• Líneas $M+K+2..M+K+Q+1$: dos números para petición de $a_i$ a $b_i$; $1 \le a_i,b_i \le N$, $a_i \ne b_i$.

Salida

• Línea $1$: número de peticiones posibles.

• Línea $2$: coste total mínimo de realizarlas.

Ejemplos

Entrada 1

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

Salida 1

1
20

Nota

Para el primer vuelo solo sirve $1 \to 2 \to 3$, coste $20$. No salen vuelos de granja $3$ y las pobres vacas quedan atrapadas.

Autores del problema: Kalki Seksaria y Richard Peng