Farmer John גילה את סוד החמאה המתוקה ביותר ב-Wisconsin: סוכר. קובייה במרעה תילקק בידי $N$ הפרות ($1\le N\le500$), ותיתן חמאה מתוקה במיוחד שניתן למכור ביוקר. כמובן הכסף הנוסף הולך למותרות לפרות.

FJ ערמומי. כמו Pavlov בעבר, הוא יודע ללמד פרות ללכת למרעה מסוים כששומעות פעמון. הוא ישים שם סוכר ויצלצל באמצע אחר הצהריים כדי שחליבת הערב תיתן חלב מושלם.

כל פרה מבלה במרעה נתון, לא בהכרח לבדה. מהמקומות והשבילים מצאו מרעה לסוכר שממזער את סכום המרחקים כשמצלצלים. השדות מקושרים מספיק כדי שתמיד יהיה פתרון.

קלט

• שורה $1$: שלמים ברווחים, מספר הפרות $N$, המרעים $P$ ($2\le P\le800$), השבילים $C$ ($1\le C\le1{,}450$). מספרים ייחודיים $1\ldots N$ לפרות ו-$1\ldots P$ למרעים.

• שורות $2\ldots N+1$: שלם, מרעה של פרה; פרה $i$ בשורה $i+1$.

• שורות $N+2\ldots N+C+1$: שלושה שלמים ברווחים, שני מרעים ואורך שביל. שבילים דו-כיווניים, לכל זוג לכל היותר אחד ישיר. שני הראשונים ב-$1\ldots P$, השלישי ב-$1\ldots225$.

פלט

• שורה $1$: שלם, סכום המרחקים המזערי של הפרות למרעה הסוכר.

דוגמאות

קלט 1

3 4 5
2
3
4
1 2 1
1 3 5
2 3 7
2 4 3
3 4 5

פלט 1

8

הסבר

התרשים מציג את החיבורים גאומטרית:

          P2  
 P1 @--1--@ C1
     \    |\
      \   | \
       5  7  3
        \ |   \
         \|    \ C3
       C2 @--5--@
          P3    P4

סוכר ב-$4$ אומר שפרה $1$ הולכת $3$ יחידות, $2$ הולכת $5$, $3$ הולכת $0$, סך הכל $8$.

מחבר הבעיה: Greg Galperin, 2001