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

---

محسن به تازگی به دلیل مشکلات مالی تغییر شغل داده و راننده تاکسی شده است. او در شهر آمل زندگی می‌کند. این شهر به صورت یک گراف بدون جهت \(n\) راسی و \(m\) یالی است که خانه‌ی محسن در راس \(h\) واقع شده است. هر کدام از یال‌های این گراف دارای وزن است که نشان دهنده مدت زمانی (واحد ثانیه) است که طول می‌کشد محسن با ماشین خودش از آن‌ها رد شود. با توجه به وضعیت مالی بد، محسن نزد بهرام رفته تا در خصوص اینکه چگونه از این شغل درآمد بیشتری کسب کند نیز از رهنمودهای بهرام استفاده کند.

بهرام به محسن می‌گوید که او از همه درخواست‌های مردم برای دربستی در روز آینده خبر دارد و به او می‌گوید با دانستن آن‌ها محسن می‌تواند بیشترین درآمد را داشته باشد. به طور مشخص بهرام به او می‌گوید در روز آینده \(k\) درخواست وجود دارد که \(i\)امین درخواست در زمان \(t_i\) و در راس \(s_i\) داده می‌شود و مقصد آن \(d_i\) است. همچنین محسن از این درخواست \(val_i\) درآمد خواهد داشت. محسن تنها زمانی می‌تواند یک درخواست را قبول کند که در زمان درخواست در \(s_i\) حاضر باشد. هچنین او می‌تواند بین سفرهای خویش در یک راس دلخواه استراحت کند و از بین مسیرهای ممکن بین مبدا و مقصد می‌تواند هر مسیری را انتخاب کند. محسن صبح از ساعت 00:00:07 صبح از خانه بیرون می‌رود و شب تا ساعت 00:00:23 می‌خواهد به خانه برسد. پس از دریافت این اطلاعات از بهرام، محسن نمی‌داند چگونه این اطلاعات به او در کسب درآمد بیشتر کمک می‌کند ولی مطمئن است که رهنمودهای بهرام مثل همیشه به او کمک خواهد کرد. به همین دلیل او از شما در کسب بیشترین درآمد روزانه با توجه به اطلاعات بهرام درخواست کمک کرده است.

ورودی

در سطر اول ورودی به ترتیب چهار عدد \(n\) و \(m\) و \(k\) و \(h\) آمده است که به ترتیب نماینگر تعداد رئوس گراف، تعداد یال هال گراف، تعداد درخواست‌ها و شماره راس خانه‌ی محسن است. \[1 \leq n \leq 500\] \[1 \leq m \leq \frac{n(n - 1)}{2}\] \[1 \leq k \leq 2000\]

در \(m\) سطر بعدی مشخصات یال‌های گراف آمده است. در سطر \(i\)اُم به ترتیب \(u\) و \(v\) و \(dis_i\) آمده است که نشان دهنده یال موجود بین \(u\) و \(v\) و طول آن یال است.

در \(k\) سطر انتهایی مشخصات درخواست‌ها آمده است. ابتدا \(s_i\) و \(d_i\) به عنوان نقاط شروع و پایان درخواست آمده اند. سپس مقدار \(val_i\) آمده است که نشان دهنده پولی است که محسن از این درخواست به دست می‌آورد. در انتها زمان درخواست به فرمت ss:mm:hh آمده است که نشان دهنده زمانی است که درخواست داده می‌شود.

\[1 \leq u, v, s_i, d_i, h \leq n\] \[1 \leq dis_i, val_i \leq 100 \, 000\]

خروجی

در تنها سطر خروجی بیشترین میزان پولی که محسن می‌تواند به دست بیاورد را چاپ کنید.

مثال‌ها

ورودی نمونه ۱

5 4 3 1
1 2 3600
2 3 3600
3 4 3600
4 5 3600
1 3 10 08:00:00
2 4 30 11:00:01
4 5 40 11:30:00

خروجی نمونه ۱

50

ورودی نمونه ۲

4 6 5 1
1 2 1800
2 3 1800
3 4 1800
4 1 1800
1 3 3800
2 4 3300
1 3 10 08:15:00
2 4 15 07:36:00
3 1 20 09:00:00
1 4 15 10:00:00
4 3 100 22:15:00

خروجی نمونه ۲

35