تربط 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$. كأي شركة عاقلة، أحد طرفي كل رحلة على الأقل مركز. لا أكثر من رحلة مباشرة لكل زوج واتجاه، ولا رحلة تبدأ وتنتهي بالمزرعة نفسها.

تدير Bessie التذاكر. للأسف، أثناء غيابها ساعات لمضغ قش لذيذ، وصل $Q$ طلب سفر لعطلات الأبقار باتجاه واحد، $1 \le Q \le 50,000$، الطلب $i$ من $a_i$ إلى $b_i$.

ساعدها إذ أثقلتها التذاكر في تحديد إمكان كل طلب وأقل تكلفته إن أمكن.

لتقليل الإخراج، اطبع فقط مجموع الطلبات الممكنة وأقل تكلفة إجمالية لها. قد لا يمكن تمثيل هذا العدد بعدد صحيح من $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