Antiga Roma (1) P73252

Considereu una civilització com la romana, tradicional i jerarquitzada. Hi ha $n$ dones nobles solteres (enumerades entre 1 i $n$) i $m$ homes nobles solters (enumerats entre 1 i $m$) en edat de casar-se, amb $n \le m$. L’emperador ha calculat, per a cada parell $(i, j)$, el benefici $M_{ij}$ que suposaria per a Roma que la dona $i$-èsima es casés amb l’home $j$-èsim.

Donada la matriu $M$, podeu fer $n$ matrimonis tot maximitzant el benefici per a Roma?

Entrada

L’entrada consisteix en diversos casos, cadascun amb $n$ i $m$, seguides de la matriu $M$: $n$ files amb $m$ naturals cadascuna. Suposeu $1 \le n \le m \le 9$, i que tots els $M_{ij}$ es troben entre 1 i $10^6$.

Sortida

Per a cada cas, escriviu el màxim benefici possible. A continuació, si hi ha més d’una solució òptima, digueu quantes n’hi ha. Altrament, si només n’hi ha una, digueu, per a cada dona entre 1 i $n$, el número del seu marit. Escriviu una línia amb 10 guions al final de cada cas.