Hãng hàng không Bovinia mở các chuyến bay kết nối n cánh đồng nơi những con bò sống. Có k cánh đồng (k ≤ n) trong số các cánh đồng trên được chọn làm trung tâm của hãng. Những cánh đồng được đánh số từ 1 đến n, trong đó các cánh đồng từ 1 đến k là những trung tâm của hãng này.

Có m chuyến bay một chiều kết nối giữa hai cánh đồng. Chuyến bay thứ i đi từ u_i đến v_i, và tốn d_i đô la.

Hãng vừa nhận được một yêu cầu gồm q chuyến du lịch một chiều. Chuyến du lịch thứ i bắt đầu từ a_i đến b_i. Để đi từ a_i đến b_i, chuyến du lịch này có thể bao gồm một dãy các chuyến bay trực tiếp (có thể đi tới một cánh đồng nhiều lần, nhưng nó phải bao gồm ít nhất một trạm trung tâm). Yêu cầu này có thể dẫn đến có một số tuyến không hợp lệ từ a_i đến b_i. Với những tuyến bay hợp lệ, bạn hãy giúp hãng hàng không Bovinia tính xem giá tiền nhỏ nhất của những chuyến bay này.

Input :

- Dòng đầu tiên chứa 4 số nguyên : n, m, k và q

- Dòng 2 -> m + 1 : dòng thứ i + 1 chứa u_i, v_i và d_i của chuyến bay i

- Dòng m + 2 -> m + q + 1 : dòng thứ m + i + 1 mô tả chuyến du lịch thứ i bao gồm a_i và b_i

Output :

- Dòng đầu tiên ghi số chuyến du lịch mà tồn tại một tuyến đường hợp lệ

- Dòng thứ hai ghi tổng số các giá tiền nhỏ nhất của các tuyến hợp lệ cho mỗi chuyến du lịch có tuyến hợp lệ

Giới hạn :

- 1 ≤ n ≤ 200

- 1 ≤ k ≤ 100

- 1 ≤ m ≤ 10000

- 1 ≤ d_i ≤ 1000000

- 1 ≤ q ≤ 10000

Ví dụ :

Input :

3 3 1 3

3 1 10

1 3 10

1 2 7

3 2

2 3

1 2

Output :

2

24