Dígits en ordre òptim P46547

Donat dos naturals $m$ i $n$, heu de construir un nombre $x$ amb els dígits $\{1, \dots, n\}$ (exactament un de cada) de manera que cap prefix (no buit) d’$x$ sigui múltiple d’$m$. Per exemple, amb $m=3$ i $n=4$, $x=2314$ no és un ordre vàlid, perquè 231 és múltiple de 3. En canvi, $x=4312$ sí que és un ordre vàlid, perquè ni 4, ni 43, ni 431, ni 4312 són múltiples de 3.

A més, teniu una matriu $M[1..n][1..n]$ tal que $M[i][j]$ indica el premi que s’aconsegueix si es posa el dígit $j$ immediatament a la dreta del dígit $i$. Maximitzeu la suma total de premis.

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb $m$ i $n$, seguits d’$M$: $n$ files, cadascuna amb $n$ naturals entre 1 i $10^6$, excepte la diagonal, que conté zeros. Podeu suposar $3 \le m \le 1000$ i $2 \le n \le 9$.

Sortida

Per a cada cas, escriviu el màxim premi possible. Si no es pot construir cap $x$, escriviu 0.