* $1$ ≤ $R$, $C$ ≤ $1500$
* Pentru 40% din teste $1$ ≤ $R$, $C$ ≤ $750$
* Pentru 70% din teste $1$ ≤ $R$, $C$ ≤ $1300$

* 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 xp < yp i ş x1 = y1, x2 = y2,..., xp-1 = yp-1.

* Spunem că un drum A=(a~1~,a~2~,..,a~R+C-1~) este mai mic lexicografic decât un drum B=(b~1~, b~2~,..,b~R+C-1~) dacă există o pozi ie ţ p astfel încât x~p~ < y~p~ şi x~1~ = y~1~, x~2~ = y~2~,..., x~p-1~ = y~p-1~.

h2. Exemplu