Air Bovinia 的航班連接乳牛居住的 $N$ 個農場，$1 \le N \le 20,000$。和其他航空公司一樣，其中 $K$ 個指定為樞紐，$1 \le K \le 200,$ $K \le N$。

目前有 $M$ 個單向航班，$1 \le M \le 20,000$。第 $i$ 個從 $u_i$ 飛到 $v_i$，費用 $d_i$ 美元，$1 \le d_i \le 10{,}000$。像其他合理的航空公司一樣，每個航班的 $u_i$、$v_i$ 至少一個是樞紐。任意方向上兩農場間至多一個直達航班，沒有航班起終點相同。

Bessie 負責票務服務。不幸的是，牠離開幾小時嚼美味乾草時，收到了 $Q$ 個乳牛假期的單程旅行請求，$1 \le Q \le 50,000$。第 $i$ 個從 $a_i$ 到 $b_i$。

Bessie 被處理這些票務的工作壓得喘不過氣，請幫牠判斷每個請求是否可實現，以及可實現時的最低費用。

為了減少輸出，只輸出可實現的請求總數和其最低總費用。注意，這個數可能超出 $32$ 位元整數。

輸入格式

• 第 $1$ 行：整數 $N$、$M$、$K$、$Q$。

• 第 $2..M+1$ 行：第 $i+1$ 行包含 $u_i$、$v_i$、$d_i$，$1 \le u_i,v_i \le N$，$u_i \ne v_i$。

• 第 $M+2..M+K+1$ 行：每行一個樞紐編號，範圍 $1..N$。

• 第 $M+K+2..M+K+Q+1$ 行：每行兩個數，表示從 $a_i$ 到 $b_i$ 的請求，$1 \le a_i,b_i \le N$，$a_i \ne b_i$。

輸出格式

• 第 $1$ 行：可實現請求數。

• 第 $2$ 行：實現所有可行請求的最低總費用。

範例

輸入格式 1

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

輸出格式 1

1
20

說明

第一趟航程唯一可行路線是 $1 \to 2 \to 3$，費用 $20$。沒有離開農場 $3$ 的航班，可憐的乳牛被困在那裡。

題目作者：Kalki Seksaria 和 Richard Peng