Air Bovinia nối $N$ trang trại nơi bò sống ($1 \le N \le 200$). Hãng chọn $K$ trang trại làm trung tâm ($1 \le K \le 100,$ $K \le N$). Trang trại đánh số $1..N$, các trung tâm là $1..K$.

Có $M$ chuyến bay một chiều ($1 \le M \le 10,000$). Chuyến $i$ từ $u_i$ đến $v_i$, giá $d_i$ đô la ($1 \le d_i \le 1,000,000$).

Nhận $Q$ yêu cầu đi một chiều ($1 \le Q \le 10,000$), yêu cầu $i$ từ $a_i$ đến $b_i$. Từ $a_i$ đến $b_i$ có thể dùng bất kỳ chuỗi chuyến bay trực tiếp, thậm chí thăm một trang trại nhiều lần, nhưng phải có ít nhất một trung tâm; có thể là điểm đi, điểm đến hoặc trung gian. Do đó có thể không có tuyến hợp lệ từ $a_i$ đến $b_i$. Với các yêu cầu còn lại, tìm chi phí hợp lệ nhỏ nhất.

Dữ liệu vào

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

• Các dòng $2..1+M$: dòng $i+1$ chứa $u_i$, $v_i$, $d_i$ của chuyến $i$.

• Các dòng $2+M..1+M+Q$: dòng $1+M+i$ mô tả yêu cầu $i$ bằng $a_i$ và $b_i$.

Dữ liệu ra

• Dòng $1$: số yêu cầu trong $Q$ có tuyến hợp lệ.

• Dòng $2$: tổng chi phí nhỏ nhất của tất cả yêu cầu có tuyến hợp lệ.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

2
24

Ghi chú

Có $3$ trang trại đánh số $1\ldots3$, $1$ là trung tâm. Chuyến từ $3$ đến $1$ giá $10$, v.v. Yêu cầu $3\to2$, $2\to3$, $1\to2$.

$3\to2$ chỉ có một tuyến giá $10+7$. $2\to3$ không có tuyến vì không có chuyến rời $2$. $1\to2$ chỉ có một tuyến hợp lệ giá $7$.

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