MODK
تعطیلات تابستانی تمام شده و «مُدکا» باید از خانه به دانشگاه برگردد. کشوری که مدکا در آن زندگی میکند شامل $n$ شهر است که با اعداد $1$ تا $n$ شمارهگذاری شدهاند. خانهی مدکا در شهر شمارهی $1$ و دانشگاهش در شهر شمارهی $n$ قرار دارد. او برای رفتن از خانه به دانشگاه میخواهد از هواپیما استفاده کند. همانطور که از نام او مشخص است، باقیماندهی اعداد بر $k$ برای او مهم است، به همین دلیل او میخواهد تعداد پروازهایی که برای رسیدن به دانشگاه انجام میدهد، بر $k$ بخشپذیر باشد. در عینحال او قصد دارد هر چه زودتر به دانشگاهش برسد، برای همین میخواهد مجموع زمان پروازهایش در بین تمامی حالتهایی که تعداد پروازهایشان بر $k$ بخشپذیر است، کمینه باشد. دقت کنید که مدکا میتواند از یک پرواز بیش از یکبار استفاده کند. همچنین ممکن است او در بین راه نیز به شهر دانشگاهش برسد ولی چون تعداد پروازهایش بر $k$ بخشپذیر نیست، به پروازهایش ادامه دهد تا به هدفش برسد.
شما باید برنامهای بنویسید که با گرفتن اطلاعات مربوط به پروازها و عدد $k$، کمترین زمان رسیدن مدکا از خانه به دانشگاه را مشخص کند به شرطی که تعداد این پروازها بر $k$ بخشپذیر باشد. در صورتی که این کار امکانپذیر نباشد، برنامهی شما باید عدد $-1$ را به عنوان جواب در نظر بگیرد.
ورودی
در سطر اول ورودی سه عدد صحیح $n$، تعداد شهرها، $m$، تعداد پروازها، و $k$ آمده است.
در هر یک از $m$ سطر بعدی به ترتیب سه عدد طبیعی $u$، $v$ و $t$ آمده است که نشاندهندهیک پرواز از شهر $u$ به $v$ در $t$ واحد زمان است. دقت کنید که پروازها یک طرفه هستند.
خروجی
در تنها سطر خروجی پاسخ مسئله را چاپ کنید.
زیرمسئلهها
- زیرمسئله اول (۱۴ نمره): $k\leq 200$
- زیرمسئله دوم (۲۲ نمره): از هر شهر دقیقا یک پرواز خارج میشود.
- زیرمسئله سوم (۶۴ نمره): بدون محدودیت اضافی
محدودیتها
- $2\leq n\leq 200$
- $0\leq m\leq n\times (n-1)$
- $1\leq k\leq 10^{9}$
- $1\leq u,v\leq n$, $u \neq v$
- $1\leq t\leq 10^6$
ورودی و خروجی نمونه
| ورودی نمونه | خروجی نمونه |
|---|---|
| 3 3 7 1 2 1 2 3 1 3 1 1 | 14 |
| 3 3 3 1 2 10 2 3 20 3 1 30 | -1 |
| 4 5 3 1 2 10 2 4 20 4 1 30 2 3 40 3 2 50 | 210 |
شرح ورودی و خروجی نمونه
در ورودی نمونهی اول، از هر شهر تنها یک پرواز خروجی داریم. بنابراین حرکات مدکا یکتاست. او بعد از $2$، $5$، $8$، $11$، $14$، $17$، … پرواز به دانشگاهش میرسد. زودترین زمانی که میتواند به دانشگاهش برسد به طوری که تعداد پروازها بر $k=7$ بخشپذیر باشد، بعد از $14$ پرواز است که با توجه به زمان پروازها، دقیقا $14$ واحد زمانی طول میکشد.
در ورودی نمونهی دوم، با توجه به اینکه از هر شهر تنها یک پرواز خروجی داریم، حرکات مدکا یکتاست و با توجه به پروازها تنها بعد از $3x+2$ ($0\leq x$) پرواز مدکا میتواند به دانشگاهش برسد. در تنیجه مدکا به هیچ صورتی نمیتواند به هدفش برسد.
در ورودی نمونهی سوم، مدکا میتواند با طی کردن پروازهای یکم، چهارم، پنجم، چهارم، پنجم و در آخر پرواز دوم به دانشگاهش برسد.