# رکورد بیشترین پرواز time limit per test: 3 seconds memory limit per test: 128 megabytes ---------- سینا می‌خواهد رکورد بیشترین تعداد پرواز با هواپیما را بشکند. او می‌خواهد در طول $k$ روز، هر روز از یک شهر به شهر دیگر پرواز کند و در نهایت در شهری که نمایندگی گینس در آن‌جا حضور دارد، رکورد خود را به ثبت برساند. مشکلی که سینا با آن برخورد کرده کمبود بودجه است. بنابراین او می‌خواهد با صرف کمترین هزینه این رکورد را به ثبت برساند. روش کار سینا به این صورت است که در روز اول از بین شهرهایی که از شهر ۱ به آن‌ها پروازی وجود دارد، شهری مانند $a$ را انتخاب کرده و به آن شهر می‌رود. سپس در روز دوم از شهر $a$ پروازی را به مقصد شهر $b$ انتخاب می‌کند و این کار ادامه پیدا می‌کند تا در نهایت در روز $k$ام به شهر مقصد که نمایندگی گینس در آن‌جا است، یعنی شهر $n$ام برسد. مشکل دیگری که سینا دارد این است که قیمت پرواز از شهر $x$ به شهر $y$ در روزهای مختلف ممکن است متفاوت باشد، اما یک دنباله متناوب است. بنابراین اگر دوره تناوب این دنباله برای پرواز از $x$ به $y$ برابر $d$ باشد، قیمت روز $d+1$ام با روز اول برابر است و به همین ترتیب برای سایر روزها. حال شما باید به سینا کمک کنید تا برنامه سفرش را با کمترین هزینه پیدا کند. ## ورودی ورودی شامل تعدادی مورد تست است. خط اول هر مورد تست، به ترتیب مقادیر $n$ و $k$ ( $2 \le n \le 10$ و $1 \le k \le 1000$ ) داده می‌شود. در ادامه در $n(n-1)$ خط بعدی برنامه پروازها از شهری به شهر دیگر داده شده است. $n-1$ خط اول برنامه پرواز از مبدأ شهر ۱ به مقصد شهرهای ۲ تا $n$، $n-1$ خط بعدی برنامه پرواز از شهر ۲ به شهرهای ۱ تا $n$ بجز ۱ و .... هر خط برنامه پرواز شامل عدد $d$ (دوره تناوب دنباله قیمت پرواز از مبدأ به مقصد) و $d$ عدد صحیح نامنفی که قیمت بلیت هواپیما در روز اول تا $d$ام است. قیمت ۰ به معنای آن است که در این روز پروازی از مبدأ به مقصد وجود ندارد. ورودی با مقدار ۰ برای $n$ و $k$ خاتمه می‌یابد. ## خروجی به ازای هر مورد تست، در خروجی کمترین هزینه برای انجام این سفر را در یک خط چاپ کنید. در صورتی که انجام این سفر ممکن نباشد، عبارت 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 خروجی 460 No Solution