Dígits en ordre òptim P46547

Donat dos naturals m i n, heu de construir un nombre x amb els dígits {1, …, 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⁶, excepte la diagonal, que conté zeros. Podeu suposar 3 ≤ m ≤ 1000 i 2 ≤ n ≤ 9.

Sortida

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