Yönləndirmə

Lukaş idman yönləndirməsini çox sevir - bu, çətin ərazidə nəzarət nöqtələrini tapmağı tələb edən bir idman növüdür. NWERC iştirakçılarını əyləndirmək üçün Lukaş yönləndirmə yarışması təşkil etmək istəyir. Lakin, iştirakçılar üçün bu soyuq İsveç noyabr havasında açıq havada yarış keçirmək çox sərt olardı, buna görə də o, yarışları qapalı məkanda - Linköping Universitetinin B binasında keçirməyə qərar verdi.

Lukaş artıq nəzarət nöqtələrinin yerlərini müəyyən edib. O, həmçinin yarışın dəqiq müddəti barədə qərar verib, buna görə də yalnız nəzarət nöqtələrini hansı ardıcıllıqla ziyarət etməli olduğunu qərarlaşdırmaq qalır ki, yarışın ümumi müddəti onun istədiyi kimi olsun. Çünki bu həmişə mümkün deyil, o, sizdən ona kömək edəcək bir proqram yazmağı xahiş edir.

Giriş Məlumatları

Aşağıdakılardan ibarətdir:

• n (2 ≤ n ≤ 14) və L (1 ≤ L ≤ 10^15) iki ədədindən ibarət bir sıra - nəzarət nöqtələrinin sayı və yarışların arzu olunan uzunluğu;

• n sətirdə n tam ədəd. i-ci sətirdəki j-ci ədəd d[ij] nəzarət nöqtələri i və j arasındakı məsafəni göstərir (1 ≤ d[ij] ≤ L üçün i ≠ j və d[ii] = 0). Bütün 1 ≤ i, j, k ≤ n üçün d[ij] = d[ji] və d[ij] ≤ d[ik] + d[kj] şərti doğrudur.

Çıxış Məlumatları

Əgər bütün nəzarət nöqtələrini bir dəfə ziyarət etmək və birincisinə qayıtmaq mümkün olarsa, belə ki, ümumi keçilən məsafə dəqiq L-ə bərabər olsun, "possible" yazın. Əks halda "impossible" yazın.

Nümunələr