D


رکورد بیشترین پرواز🔗

time limit per test: 3 seconds

memory limit per test: 128 megabytes


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

روش کار سینا به این صورت است که در روز اول از بین شهرهایی که از شهر ۱ به آن‌ها پروازی وجود دارد، شهری مانند aa را انتخاب کرده و به آن شهر می‌رود. سپس در روز دوم از شهر aa پروازی را به مقصد شهر bb انتخاب می‌کند و این کار ادامه پیدا می‌کند تا در نهایت در روز kkام به شهر مقصد که نمایندگی گینس در آن‌جا است، یعنی شهر nnام برسد. مشکل دیگری که سینا دارد این است که قیمت پرواز از شهر xx به شهر yy در روزهای مختلف ممکن است متفاوت باشد، اما یک دنباله متناوب است. بنابراین اگر دوره تناوب این دنباله برای پرواز از xx به yy برابر dd باشد، قیمت روز d+1d+1ام با روز اول برابر است و به همین ترتیب برای سایر روزها. حال شما باید به سینا کمک کنید تا برنامه سفرش را با کمترین هزینه پیدا کند.

ورودی🔗

ورودی شامل تعدادی مورد تست است. خط اول هر مورد تست، به ترتیب مقادیر nn و kk ( 2n102 \le n \le 10 و 1k10001 \le k \le 1000 ) داده می‌شود. در ادامه در n(n1)n(n-1) خط بعدی برنامه پروازها از شهری به شهر دیگر داده شده است. n1n-1 خط اول برنامه پرواز از مبدأ شهر ۱ به مقصد شهرهای ۲ تا nn، n1n-1 خط بعدی برنامه پرواز از شهر ۲ به شهرهای ۱ تا nn بجز ۱ و .... هر خط برنامه پرواز شامل عدد dd (دوره تناوب دنباله قیمت پرواز از مبدأ به مقصد) و dd عدد صحیح نامنفی که قیمت بلیت هواپیما در روز اول تا ddام است. قیمت ۰ به معنای آن است که در این روز پروازی از مبدأ به مقصد وجود ندارد. ورودی با مقدار ۰ برای nn و kk خاتمه می‌یابد.

خروجی🔗

به ازای هر مورد تست، در خروجی کمترین هزینه برای انجام این سفر را در یک خط چاپ کنید. در صورتی که انجام این سفر ممکن نباشد، عبارت No Solution را چاپ کنید.

مثال🔗

ورودی

3 6
2 130 150
3 75 0 80
7 120 110 0 100 110 120 0
4 60 70 60 50
3 0 135 140
2 70 80
2 3
2 0 700
1 80
0 0
Plain text

خروجی

460
No Solution
Plain text