Assignment Problem: Optimal Task Allocation

There are n tasks to be assigned to n persons. The benefit when person \(i\) does task \(j\) is given by \(c_{ij}\). You are required to design an assignment scheme that achieves either the minimum or maximum total benefit.

The input contains a positive integer \(n\), followed by a string indicating the optimization objective (min for minimum or max for maximum), and an \(n \times n\) matrix representing the benefits \(c_{ij}\). The output is a single integer representing the optimal total benefit under the given objective.

inputFormat

The first line contains a positive integer \(n\) (the number of tasks/persons).
The second line contains a string: either min (to minimize the total benefit) or max (to maximize the total benefit).
The following \(n\) lines each contain \(n\) space-separated integers representing the matrix \(c_{ij}\>.

outputFormat

Output a single integer representing the optimal total benefit based on the chosen objective.

sample

3
min
1 2 3
4 5 6
7 8 9

15