407948: GYM102947 I Food Allocation II

After a local forest tour gone wrong, you and $$$n$$$ other survivors have been stranded in the wilderness. Due to your incredible leadership skills, you have taken command of the rest of the survivors and need to organize them in order to get the necessary supplies to survive.

There are $$$n$$$ different types of food that each of the $$$n$$$ survivors can collect. Each survivor can collect any of the types of food, but they each have different skill levels at collecting each type of food, which represent the amount of that food that they can collect.

You must assign each survivor to a single food type and ensure that your camp has a survivor assigned to each food type to maximize the value of the food you get. In this case, the survivors take the food they collected for themselves but refuse to take any food above the minimum food collected by any other survivor to prevent jealousy from tearing apart the group, so the value of the assignment is the min of all the food collected by each survivor. How do you maximize this assignment of survivors?

The first line will consist of a single integer $$$n$$$ ($$$2 \leq n \leq 500$$$) giving the number of survivors. The next $$$n$$$ lines will each consist of $$$n$$$ integers where the $$$j$$$th integer on the $$$i$$$th line, $$$s_{ij}$$$ ($$$0 \leq s_{ij} \leq 10^5$$$), gives the skill point value for survivor $$$i$$$ when it is assigned food type $$$j$$$.

Output a single integer giving the total value of the optimal assignment of survivors to tasks.

3
3 2 3
2 1 1
1 2 3

2

One optimal assignment is to assign the first survivor to the second food type, the second survivor to the first food type, and the third survivor to the third food type, which gives a value of $$$2$$$.