A square array A[1..N, 1..N] of positive integers is given. Design an algorithm, that will select N values from this array so that exactly one value from each column and each row is selected and the sum of these values is minimal (over all possible selections).

• Describe this algorithm and give its pseudocode.

• Briefly justify its correctness.

• Estimate its time and space complexity.