Air Bovinia nối $N$ trang trại bò bằng chuyến bay, $1 \le N \le 20,000$. Như mọi hãng, chỉ định $K$ trung tâm, $1 \le K \le 200,$ $K \le N$.

Có $M$ chuyến một chiều, $1 \le M \le 20,000$. Chuyến $i$ từ $u_i$ tới $v_i$ giá $d_i$ đô la, $1 \le d_i \le 10{,}000$. Như hãng hợp lý, ít nhất một đầu mỗi chuyến là trung tâm. Mỗi cặp theo mỗi chiều có tối đa một chuyến trực tiếp, không chuyến nào cùng nơi đi đến.

Bessie quản lý vé. Tiếc là trong vài giờ đi nhai cỏ khô ngon, nhận $Q$ yêu cầu du lịch nghỉ lễ một chiều của bò, $1 \le Q \le 50,000$, yêu cầu $i$ từ $a_i$ tới $b_i$.

Giúp Bessie quá tải kiểm tra từng yêu cầu và chi phí nhỏ nhất nếu làm được.

Để giảm đầu ra, chỉ in tổng số yêu cầu khả thi và tổng chi phí nhỏ nhất của chúng. Số này có thể không vừa số nguyên $32$ bit.

Dữ liệu vào

• Dòng $1$: số nguyên $N$, $M$, $K$, $Q$.

• Các dòng $2..M+1$: dòng $i+1$ chứa $u_i$, $v_i$, $d_i$; $1 \le u_i,v_i \le N$, $u_i \ne v_i$.

• Các dòng $M+2..M+K+1$: mỗi dòng mã trung tâm trong $1..N$.

• Các dòng $M+K+2..M+K+Q+1$: hai số mỗi dòng yêu cầu từ $a_i$ tới $b_i$; $1 \le a_i,b_i \le N$, $a_i \ne b_i$.

Dữ liệu ra

• Dòng $1$: số yêu cầu khả thi.

• Dòng $2$: tổng chi phí nhỏ nhất thực hiện chúng.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

1
20

Ghi chú

Chuyến đầu chỉ có tuyến $1 \to 2 \to 3$, giá $20$. Không chuyến rời trang trại $3$, nên bò tội nghiệp mắc kẹt.

Tác giả bài toán: Kalki Seksaria và Richard Peng