Air Bovinia đang lên kế hoạch kết nối \(N\) trang trại nơi các cô bò sinh sống (\(1 \le N \le 200\)). Giống như mọi hãng hàng không khác, \(K\) trong số các trang trại này (\(1 \le K \le 100\), \(K \le N\)) đã được chọn làm trung tâm. Các trang trại được đánh số thuận tiện từ \(1\) đến \(N\), trong đó các trang trại từ \(1\) đến \(K\) là các trung tâm.

Hiện có \(M\) chuyến bay một chiều (\(1 \le M \le 10\,000\)) kết nối các trang trại. 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 1\,000\,000\)).

Gần đây, hãng hàng không nhận được yêu cầu cho \(Q\) hành trình một chiều (\(1 \le Q \le 10\,000\)). Hành trình thứ \(i\) đi từ trang trại \(a_i\) đến trang trại \(b_i\). Để đi từ \(a_i\) đến \(b_i\), hành trình có thể gồm một dãy bất kỳ các chuyến bay thẳng, thậm chí có thể ghé cùng một trang trại nhiều lần, nhưng phải đi qua ít nhất một trung tâm; trung tâm đó có thể là điểm xuất phát, điểm đến hoặc không phải cả hai. Điều kiện này có thể khiến một số yêu cầu không có lộ trình hợp lệ. Với mọi yêu cầu còn lại, hãy giúp Air Bovinia xác định chi phí nhỏ nhất của một lộ trình hợp lệ.

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\), mô tả chuyến bay thứ \(i\).
• \(Q\) dòng cuối, dòng thứ \(i\) chứa \(a_i\) và \(b_i\), mô tả hành trình thứ \(i\).

Ràng buộc

• \(1 \le N \le 200\).
• \(1 \le K \le 100\) và \(K \le N\); các trang trại \(1,2,\ldots,K\) là các trung tâm.
• \(1 \le M \le 10\,000\).
• \(1 \le d_i \le 1\,000\,000\).
• \(1 \le Q \le 10\,000\).

Dữ liệu ra

• Dòng đầu tiên chứa số hành trình trong \(Q\) yêu cầu có tồn tại lộ trình hợp lệ.
• Dòng thứ hai chứa tổng chi phí nhỏ nhất của tất cả các hành trình có lộ trình hợp lệ, trong đó mỗi hành trình được tính theo chi phí nhỏ nhất có thể của nó.

Ví dụ

3 3 1 3
3 1 10
1 3 10
1 2 7
3 2
2 3
1 2

2
24

Nguồn

USACO 2013 December Contest, Silver — Problem 2: Vacation Planning

Tác giả: Kalki Seksaria, 2013.