Air Bovinia는 소들이 사는 $N$개 농장을 항공편으로 잇습니다. $1 \le N \le 20,000$. 다른 항공사처럼 $K$개를 허브로 정했고 $1 \le K \le 200,$ $K \le N$입니다.

현재 $M$개 편도 항공편이 있으며 $1 \le M \le 20,000$입니다. $i$는 $u_i$에서 $v_i$로 가고 비용은 $d_i$달러, $1 \le d_i \le 10{,}000$입니다. 합리적인 항공사답게 매 편의 양 끝 중 적어도 하나는 허브입니다. 한 방향 농장 쌍에 직항은 최대 하나이고 출발 도착 농장이 같을 수 없습니다.

Bessie는 발권 담당입니다. 안타깝게도 맛있는 건초를 씹으러 몇 시간 나간 동안 소들의 휴가 편도 여행 요청 $Q$개 ($1 \le Q \le 50,000$)가 들어왔습니다. $i$번째는 $a_i$에서 $b_i$입니다.

발권 업무에 지친 그녀를 도와 각 요청이 가능한지, 가능하면 최소 비용을 구하세요.

출력을 줄이려 가능한 요청 수와 그 최소 총비용만 출력합니다. 이 수는 $32$비트 정수에 들어가지 않을 수 있습니다.

입력

• 줄 $1$: 정수 $N$, $M$, $K$, $Q$.

• 줄 $2..M+1$: 줄 $i+1$에 $u_i$, $v_i$, $d_i$, $1 \le u_i,v_i \le N$, $u_i \ne v_i$.

• 줄 $M+2..M+K+1$: 한 줄에 $1..N$ 범위 허브 번호 하나.

• 줄 $M+K+2..M+K+Q+1$: 줄마다 두 수는 $a_i$에서 $b_i$ 요청이며 $1 \le a_i,b_i \le N$, $a_i \ne b_i$.

출력

• 줄 $1$: 가능한 요청 수.

• 줄 $2$: 가능한 요청들을 수행하는 최소 총비용.

예제

입력 1

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

출력 1

1
20

참고

첫 비행은 $1 \to 2 \to 3$만 가능하며 비용 $20$입니다. 농장 $3$에서 떠나는 편이 없어 불쌍한 소들이 갇혀 있습니다.

문제 작성자: Kalki Seksaria와 Richard Peng