Preu mínim P20023

Teniu n tasques a realitzar, i n treballadors que poden fer-les. Per a cada tasca 1 ≤ i ≤ n i cada treballador 1 ≤ j ≤ n, p[i][j] és el preu de que el treballador i faci la tasca j.

Feu un programa que calculi el preu mínim d’assignar exactament una tasca diferent a cada treballador.

Entrada

L’entrada consisteix en un natural 1 ≤ n ≤ 10, seguit de p, la matriu n × n de preus (n línies amb n naturals entre 1 i 1000).

Sortida

Escriviu el preu mínim d’assignar exactament una tasca diferent a cada treballador.

Observació

Existeixen algorismes de cost polinòmic per resoldre aquest problema, però són difícils de programar. Implementeu un backtracking.