تخطط Air Bovinia لربط $N$ مزارع تعيش فيها الأبقار ($1 \le N \le 200$). تختار $K$ مزارع كمراكز ربط ($1 \le K \le 100,$ $K \le N$). ترقم المزارع $1..N$، والمراكز $1..K$.

توجد $M$ رحلات جوية باتجاه واحد ($1 \le M \le 10,000$). الرحلة $i$ من $u_i$ إلى $v_i$ وتكلف $d_i$ دولارًا ($1 \le d_i \le 1,000,000$).

وصلت $Q$ طلبات سفر باتجاه واحد ($1 \le Q \le 10,000$)، الطلب $i$ من $a_i$ إلى $b_i$. من $a_i$ إلى $b_i$ يمكن استخدام أي تسلسل رحلات مباشرة، حتى تكرار زيارة المزرعة، لكن يجب تضمين مركز واحد على الأقل، وقد يكون البداية أو الوجهة أو مزرعة وسطية. لذا قد لا يوجد مسار صالح من $a_i$ إلى $b_i$. لباقي الطلبات أوجد أقل تكلفة مسار صالح.

الإدخال

• السطر $1$: الأعداد الصحيحة $N$ و$M$ و$K$ و$Q$.

• الأسطر $2..1+M$: السطر $i+1$ يحتوي $u_i$ و$v_i$ و$d_i$ للرحلة $i$.

• الأسطر $2+M..1+M+Q$: السطر $1+M+i$ يصف الطلب $i$ عبر $a_i$ و$b_i$.

الإخراج

• السطر $1$: عدد الطلبات من $Q$ التي لها مسار صالح.

• السطر $2$: مجموع أقل تكاليف جميع الطلبات ذات المسار الصالح.

أمثلة

الإدخال 1

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

الإخراج 1

2
24

ملاحظة

توجد $3$ مزارع مرقمة $1\ldots3$، و$1$ مركز. الرحلة من $3$ إلى $1$ تكلف $10$، وهكذا. الطلبات $3\to2$ و$2\to3$ و$1\to2$.

$3\to2$ له مسار وحيد بتكلفة $10+7$. $2\to3$ بلا مسار لأن لا رحلة تغادر $2$. $1\to2$ له مسار صالح وحيد بتكلفة $7$.

مؤلف المسألة: Kalki Seksaria