راننده تاکسی


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

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

بهرام به محسن می‌گوید که او از همه درخواست‌های مردم برای دربستی در روز آینده خبر دارد و به او می‌گوید با دانستن آن‌ها محسن می‌تواند بیشترین درآمد را داشته باشد. به طور مشخص بهرام به او می‌گوید در روز آینده kk درخواست وجود دارد که iiامین درخواست در زمان tit_i و در راس sis_i داده می‌شود و مقصد آن did_i است. همچنین محسن از این درخواست valival_i درآمد خواهد داشت. محسن تنها زمانی می‌تواند یک درخواست را قبول کند که در زمان درخواست در sis_i حاضر باشد. هچنین او می‌تواند بین سفرهای خویش در یک راس دلخواه استراحت کند و از بین مسیرهای ممکن بین مبدا و مقصد می‌تواند هر مسیری را انتخاب کند. محسن صبح از ساعت 00:00:07 صبح از خانه بیرون می‌رود و شب تا ساعت 00:00:23 می‌خواهد به خانه برسد. پس از دریافت این اطلاعات از بهرام، محسن نمی‌داند چگونه این اطلاعات به او در کسب درآمد بیشتر کمک می‌کند ولی مطمئن است که رهنمودهای بهرام مثل همیشه به او کمک خواهد کرد. به همین دلیل او از شما در کسب بیشترین درآمد روزانه با توجه به اطلاعات بهرام درخواست کمک کرده است.

ورودی🔗

در سطر اول ورودی به ترتیب چهار عدد nn و mm و kk و hh آمده است که به ترتیب نماینگر تعداد رئوس گراف، تعداد یال هال گراف، تعداد درخواست‌ها و شماره راس خانه‌ی محسن است. 1n5001 \leq n \leq 500 1mn(n1)21 \leq m \leq \frac{n(n - 1)}{2} 1k20001 \leq k \leq 2000

در mm سطر بعدی مشخصات یال‌های گراف آمده است. در سطر iiاُم به ترتیب uu و vv و disidis_i آمده است که نشان دهنده یال موجود بین uu و vv و طول آن یال است.

در kk سطر انتهایی مشخصات درخواست‌ها آمده است. ابتدا sis_i و did_i به عنوان نقاط شروع و پایان درخواست آمده اند. سپس مقدار valival_i آمده است که نشان دهنده پولی است که محسن از این درخواست به دست می‌آورد. در انتها زمان درخواست به فرمت ss:mm:hh آمده است که نشان دهنده زمانی است که درخواست داده می‌شود.

1u,v,si,di,hn1 \leq u, v, s_i, d_i, h \leq n 1disi,vali1000001 \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
Plain text

خروجی نمونه ۱🔗

50
Plain text

ورودی نمونه ۲🔗

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
Plain text

خروجی نمونه ۲🔗

35
Plain text