Maximizing Secret Santa Preference

In this problem, you are given an integer (N) representing the number of employees and an (N \times N) matrix of preference values. The element in the (i)-th row and (j)-th column, denoted by (p_{i,j}), represents the preference value if the (i)-th employee is assigned to the (j)-th task (or recipient). Your goal is to find a one-to-one assignment of employees to tasks such that the total preference value [ \text{Total} = \sum_{i=1}^{N} p_{i,\pi(i)} ] is maximized, where (\pi) is a permutation of ({1, 2, \dots, N}).

This is a typical assignment problem which can be solved using dynamic programming with bitmasking (given the small constraints) or the Hungarian algorithm. The input size in the given test cases is small (i.e., (N \le 5)), so an (O(N\cdot2^N)) solution is efficient enough.

inputFormat

The first line of input contains a single integer (N), the number of employees. This is followed by (N) lines, each containing (N) space-separated integers. The (j)-th integer in the (i)-th line represents the preference value (p_{i,j}).

outputFormat

Output a single integer, which is the maximum total preference value achievable by an optimal assignment.## sample

3
3 1 2
1 3 2
2 1 3

9