• محدودیت زمان: ۱٫۵ ثانیه
• محدودیت حافظه: ۵۱۲ مگابایت
• روز ۲ دوره ۳۱

---

علی بعد از دیدن فیلم انگاشته (Tenet) ایده‌ی سوال زیر به ذهنش رسید ولی توانایی حل آن را نداشت. به وی کمک کنید تا آن را حل کند.

کیانوش ناباورانه به شهر عجیب غریبی به اسم برره می‌رسد. در برره \(n\) روستا وجود دارد که بعضی از آن‌ها با \(m\) جاده دوطرفه به هم متصل شده‌اند، به طوری که از هر روستا می‌توان به بقیه روستاها رفت. جاده‌ی \(i\)ام روستای \(v_i\) و \(u_i\) را به هم وصل می‌کند. برای اینکه کیانوش از جاده \(i\)ام عبور کند، نظام دوبرره از او \(a_i\) ریال می‌گیرد و به او کوپن جاده‌ی \(i\)ام را می‌دهد. همچنین او می‌تواند هنگام گذرکردن از جاده \(i\)ام کوپن همان جاده را به نظام دوبرره پس بدهد و با پرداخت \(b_i\) ریال از آن عبور کند. در روش دوم نظام دوبرره به کیانوش کوپن نمی‌دهد.

کیانوش که در حین تبعید شدن سر از برره درآورده است، کیفی به همراه خودش ندارد و کوپن‌ها را در جیبش قرار می‌دهد. او فقط می‌تواند کوپنی را به بالای جیبش اضافه کند یا بالاترین کوپن درون جیبش را دربیاورد. اگر کیانوش کوپنی که نظام دوبرره به او می‌دهد را در جیبش قرار ندهد و یا اگر کوپنی را از جیبش دربیاورد ولی فورا از آن استفاده نکند، نظام دوبرره حکم اعدام او را صادر می‌کند! به همین دلیل کیانوش هیچگاه این کار را انجام نمی‌دهد.

برای گرفتن اقامت برره، کیانوش باید به تعدادی روستا برود و رضایت اهالی آنجا را کسب کند. کیانوش دنباله \(\langle x_1, x_2, ..., x_k \rangle\) روستاها را دارد و باید آن روستاها را به ترتیب ببیند. او از روستای \(x_1\) شروع می‌کند، سپس باید با طی کردن تعدادی جاده به روستای \(x_2\) برود، سپس با طی کردن تعدادی جاده دیگر به روستای \(x_3\) برود، ... و در نهایت به روستای \(x_k\) برود. کیانوش به حداقل چقدر پول احتیاج دارد تا بتواند اقامت برره را بگیرد.

ورودی

در خط اول سه عدد \(n\) تعداد روستاها، \(m\) تعداد جاده‌ها و \(k\) طول دنباله‌ی روستاها به ترتیب می‌آیند.

در \(i\)امین خط از \(m\) خط بعدی، چهار عدد \(v_i\)، \(u_i\)، \(a_i\) و \(b_i\) نمایانگر جاده \(i\)ام به ترتیب می‌آیند.

در خط بعدی \(k\) عدد \(x_1, x_2, ..., x_k\) به ترتیب می‌آیند.

تضمین می‌شود گراف شهر برره همبند است.

\[1 \leq n, k \leq 150\] \[n-1 \leq m \leq \binom{n}{2}\]

\[1 \le u_i, v_i \le n,~~ u_i \neq v_i\]

\[1 \le b_i \le a_i \le 10^9\]

خروجی

در خروجی تنها یک عدد خروجی دهید که کمترین پولی است که کیانوش برای گرفتن اقامت باید به نظام دوبرره پرداخت کند.

زیرمسئله‌ها

زیرمسئله	نمره	محدودیت
۱	۶	\(a_i = b_i\)
۲	۸	\(m = n - 1\)
۳	۱۰	\(k = 3\)
۴	۱۵	\(k = 4\)
۵	۳۰	\(n, k \leq 50\)
۶	۳۱	بدون محدودیت اضافی

مثال

ورودی نمونه ۱

4 6 10
1 2 3 1
1 3 4 2
1 4 6 3
2 3 1 1
2 4 3 2
3 4 8 4
1 4 2 3 2 4 1 3 2 4

خروجی نمونه ۱

24

ورودی نمونه ۲

5 4 6
1 4 5 2
4 2 4 1
4 3 3 2
1 5 6 3
5 2 3 1 1 5

خروجی نمونه ۲

26

ورودی نمونه ۳

7 8 3
1 2 5 1
2 4 5 1
1 3 4 3
3 4 4 3
4 5 3 1
5 7 3 1
4 6 3 2
6 7 2 1
1 7 1

خروجی نمونه ۳

20