Ocean şi echipa sa au decis că e momentul să mai dea o lovitură la un casino. Pentru aceasta l-au cooptat în echipa pe al XIV-lea membru, Ovi, expert în alarme (şi mai ales în dezactivarea lor!). Când echipa se adună, Ovi le spune:
- Banii sunt în casino la ultimul etaj. Etajul are forma pătratică şi este împărţit în N x N camere pătrate de dimensiuni egale, exact ca o matrice cu N linii şi N coloane. Să considerăm că liniile sunt numerotate de la 1 la N de sus în jos, iar coloanele de la 1 la N de la stânga la dreapta.
- Se poate intra numai prin camera aflată în colţul din stânga-sus (camera de pe linia 1 şi coloana 1) şi veţi ieşi prin camera din colţul din dreapta-jos (cea de pe linia N şi coloana N). Două camere se învecinează numai dacă au un perete comun (se află pe aceeaşi linie, respectiv coloană pe poziţii consecutive).
- În unele camere este stocată câte o sumă de bani şi nu există două camere care să conţină aceeaşi sumă. Dar sunt şi camere-capcană care nu conţin bani. În acestea să nu intraţi, căci veţi declanşa alarma! Nu vă lăcomiţi să luaţi toţi banii din toate camerele. Trebuie să mergeţi pe un drum de lungime minimă de la camera de intrare la cea de ieşire. Un drum este format dintr-o succesiune de camere care conţin bani, oricare două camere consecutive din succesiune fiind vecine. Lungimea unui drum minim este dată de numărul de camere prin care se trece. Pot fi mai multe drumuri de lungime minimă. Două drumuri sunt distincte dacă au cel puţin o camera diferită. Fiecare astfel de drum minim are asociat şirul de valori reprezentate de sumele de bani din fiecare cameră.
- Voi primi în ziua în care vom da lovitura, de la un om din interior, un număr K. Trebuie să determinaţi al K-lea şir din punct de vedere lexicografic dintre toate şirurile asociate drumurilor de lungime minima. Numai acesta este drumul optim care trebuie urmat pentru că nu va declanşa nicio alarmă.
Cerinţă
Ajutaţi echipa lui Ocean să determine rapid acest al K-lea şir din punct de vedere lexicografic.
Date de intrare
Fişierul de intrare ocean14.in conţine pe prima linie cele două numere naturale N şi K separate printr-un singur spaţiu. Pe următoarele N linii se găsesc, separate prin câte un spaţiu, câte N numere naturale reprezentând sumele de bani din fiecare cameră.
Date de ieşire
Fişierul ocean14.out va conţine pe prima linie un număr P reprezentând lungimea minimă a unui drum de la camera de start la cea de ieşire. Pe linia a doua, separate prin câte un spaţiu, se găsesc P numere naturale nenule, care reprezintă al K-lea şir din punct de vedere lexicografic asociat unui drum de lungime minimă.
Restricţii
1 ≤ N ≤ 50
Numărul total de drumuri de lungime minimă este mai mic de 2 miliarde şi este garantat că există cel puţin un drum de la camera de start la cea de ieşire.
Toate valorile strict pozitive din matrice sunt distincte două câte două 1 ≤ K ≤ numărul de drumuri de lungime minimă
Exemple
ocean14.in
ocean14.out
Explicaţii
4 2
5 3 4 0
1 0 2 0
6 10 9 11
0 0 7 8
7
5 1 6 10 9 11 8
Există 4 drumuri de lungime minima 7. Ele sunt (în ordinea lexicografică): 5 1 6 10 9 7 8
5 1 6 10 9 11 8
5 3 4 2 9 7 8
5 3 4 2 9 11 8
Al doilea în ordine lexicografică este 5 1 6 10 9 11 8