Se dă o matrice cu R linii şi C coloane de numere distincte de la 1 la R*C. Bemo, personajul emoţional, doreşte să urmărească cel mai bun drum din colţul superior stânga, de coordonate (1, 1), în colţul inferior dreapta, de coordonate (R, C).
Un drum este o secvenţă de numere din matrice în care fiecare număr se găseşte în jos sau la dreapta numărului anterior; cu alte cuvinte dacă (i, j) este poziţia unui număr de pe drum, atunci următorul număr poate fi cel de pe poziţia (i+1,j) sau cel de pe poziţia (i,j+1). Pentru a determina dacă un drum A este mai bun decât un drum B, numerele fiecărui drum se vor sorta şi se va alege cel mai mic lexicografic, e.g. [1,3,5,6,8] < [1,4,5,6,7].
Cerinţă
Să se determine cel mai bun drum pe care Bemo îl poate alege.
Date de intrare
Fişierul de intrare bemo.in conţine pe prima linie două numere naturale R şi C, unde R este numărul liniilor, iar C numărul coloanelor matricei lui Bemo. Pe următoarele R linii se vor găsi câte C numere separate printr-un spaţiu. Fiecare număr va fi unic şi va fi cuprins în intervalul [1, R*C].
Date de ieşire
Fişierul de iesire bemo.out va conţine R+C-1 numere reprezentând cel mai bun drum pe care Bemo îl poate alege. Numerele vor fi separate prin câte un spaţiu.
Restricţii
• 0 < R, C < 1250
• Spunem că un drum A=(A1,A2,...,AR+C-1) este mai mic lexicografic decât un drum B=B1, B2,...,BR+C-1) dacă există o poziţie p astfel încât Ap < Bp şi A1 = B1, A2 = B2,..., Ap-1 = Bp-1.