Air Bovinia liga as $N$ fazendas das vacas, $1 \le N \le 20,000$. Como qualquer companhia, designa $K$ centros de conexão, $1 \le K \le 200,$ $K \le N$.

Oferece $M$ voos só de ida, $1 \le M \le 20,000$. O voo $i$ vai de $u_i$ a $v_i$ por $d_i$ dólares, $1 \le d_i \le 10{,}000$. Como uma companhia sensata, ao menos uma extremidade é centro. Há no máximo um voo direto por par em cada direção, nenhum com origem e destino iguais.

Bessie cuida dos bilhetes. Infelizmente, ausente por horas mastigando feno delicioso, recebeu $Q$ pedidos de viagens de férias de ida das vacas, $1 \le Q \le 50,000$, o $i$ de $a_i$ a $b_i$.

Ajude Bessie, sobrecarregada, a verificar cada pedido e seu custo mínimo se possível.

Para reduzir a saída, imprima só o total de pedidos possíveis e o custo total mínimo. Esse número pode não caber em inteiro de $32$ bits.

Entrada

• Linha $1$: inteiros $N$, $M$, $K$, $Q$.

• Linhas $2..M+1$: a linha $i+1$ contém $u_i$, $v_i$, $d_i$; $1 \le u_i,v_i \le N$, $u_i \ne v_i$.

• Linhas $M+2..M+K+1$: um identificador de centro em $1..N$ por linha.

• Linhas $M+K+2..M+K+Q+1$: dois números para pedido de $a_i$ a $b_i$; $1 \le a_i,b_i \le N$, $a_i \ne b_i$.

Saída

• Linha $1$: número de pedidos possíveis.

• Linha $2$: custo total mínimo de realizá-los.

Exemplos

Entrada 1

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

Saída 1

1
20

Observação

Para o primeiro voo só há $1 \to 2 \to 3$, custo $20$. Não saem voos de $3$ e as pobres vacas ficam presas lá.

Autores do problema: Kalki Seksaria e Richard Peng