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$.

עזרו ל־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