h2. Restricţii
* $1$ ≤ $R$, $C$ ≤ $1500$

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

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

* 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

1404