Air Bovinia khai thác các chuyến bay kết nối \(N\) trang trại nơi các cô bò sinh sống (\(1 \le N \le 20\,000\)). Giống như mọi hãng hàng không khác, \(K\) trang trại trong số đó được chỉ định làm trung tâm (\(1 \le K \le 200\), \(K \le N\)).

Hiện tại, Air Bovinia cung cấp \(M\) chuyến bay một chiều (\(1 \le M \le 20\,000\)), trong đó chuyến bay thứ \(i\) đi từ trang trại \(u_i\) đến trang trại \(v_i\) và có giá \(d_i\) đô la (\(1 \le d_i \le 10\,000\)). Như mọi hãng hàng không hợp lý khác, đối với mỗi chuyến bay, ít nhất một trong hai trang trại \(u_i\) và \(v_i\) là một trung tâm. Giữa hai trang trại có nhiều nhất một chuyến bay thẳng theo mỗi hướng, và không chuyến bay nào bắt đầu rồi kết thúc tại cùng một trang trại.

Bessie phụ trách dịch vụ bán vé của Air Bovinia. Không may, trong lúc cô đi nhai cỏ khô ngon lành suốt vài giờ, hãng đã nhận được \(Q\) yêu cầu di chuyển một chiều cho kỳ nghỉ của các cô bò (\(1 \le Q \le 50\,000\)), trong đó yêu cầu thứ \(i\) là đi từ trang trại \(a_i\) đến trang trại \(b_i\).

Vì Bessie đang quá tải với việc xử lý những tấm vé này, hãy giúp cô xác định xem từng yêu cầu có thể được đáp ứng hay không và chi phí nhỏ nhất nếu có thể.

Để giảm kích thước dữ liệu ra, bạn chỉ cần in tổng số yêu cầu vé có thể đáp ứng và tổng các chi phí nhỏ nhất của chúng. Lưu ý rằng tổng chi phí này có thể không vừa trong một số nguyên \(32\) bit.

Dữ liệu vào

• Dòng đầu tiên chứa bốn số nguyên \(N\), \(M\), \(K\) và \(Q\).
• \(M\) dòng tiếp theo, dòng thứ \(i\) chứa \(u_i\), \(v_i\) và \(d_i\).
• \(K\) dòng tiếp theo, mỗi dòng chứa mã số của một trung tâm.
• \(Q\) dòng cuối, dòng thứ \(i\) chứa hai số \(a_i\) và \(b_i\), biểu thị một yêu cầu vé từ trang trại \(a_i\) đến trang trại \(b_i\).

Ràng buộc

• \(1 \le N \le 20\,000\).
• \(1 \le K \le 200\) và \(K \le N\).
• \(1 \le M \le 20\,000\).
• \(1 \le u_i,v_i \le N\) và \(u_i \ne v_i\).
• \(1 \le d_i \le 10\,000\).
• Mỗi chuyến bay có ít nhất một đầu mút là trung tâm; giữa hai trang trại có nhiều nhất một chuyến bay thẳng theo mỗi hướng.
• Mỗi mã số trung tâm nằm trong đoạn từ \(1\) đến \(N\).
• \(1 \le Q \le 50\,000\).
• \(1 \le a_i,b_i \le N\) và \(a_i \ne b_i\).

Dữ liệu ra

• Dòng đầu tiên chứa số yêu cầu vé có thể được đáp ứng.
• Dòng thứ hai chứa tổng các chi phí nhỏ nhất để đáp ứng những yêu cầu vé có thể thực hiện được.

Ví dụ

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

1
20

Nguồn

USACO 2013 December Contest, Gold — Problem 1: Vacation Planning (gold)

Tác giả: Kalki Seksaria và Richard Peng, 2013.