Statement

Marco is the coach of a team with N members, which just won N prizes in a prestigious international competition. Now starts the hardest part: assigning one of the prizes to each one of the team members! By being the coach, Marco has the duty of deciding an assignment of the prizes. For each team member i = 0 … N-1 and prize j = 0 … N-1, Marco knows S_ij, which represents how much member i would be satisfied by prize j. His goal is to assign a different prize P_i to each team member i, so that the total satisfaction is minimal: no easy win for his fellow comrades! However, if he assign prizes in such a way that team member i prefers prize P_j over P_i, and conversely team member j prefers P_i over P_j, the two comrades will immediately swap prizes, ruining Marco's effort to minimise his team's satisfaction. Help Marco find an assignment minimising the total satisfaction and such that no swap is possible!