All problems

Stall Setup Crew

Hard · dynamic programming

A street fair has n stalls to set up, and exactly n volunteers to do it. Every volunteer sets up one stall, and every stall is set up by one volunteer.

You are given a square table minutes. The value minutes[i][j] is how many minutes volunteer i needs to set up stall j. Volunteers work at the same time, but the organiser pays for every minute worked, so what matters is the sum of the minutes of all n volunteers.

Decide which volunteer sets up which stall, and return the smallest possible total number of minutes.

Examples

Example 1

Input: minutes = [[4, 2], [3, 5]]

Output: 5

Volunteer 0 sets up stall 1 (2 minutes) and volunteer 1 sets up stall 0 (3 minutes). The total is 5; the other way round costs 4 + 5 = 9.

Example 2

Input: minutes = [[7]]

Output: 7

With one volunteer and one stall there is only one choice.

Example 3

Input: minutes = [[1, 5, 5], [5, 1, 5], [5, 5, 1]]

Output: 3

Each volunteer takes the stall that suits them (1 minute each), so the total is 3.

Constraints

• 1 <= n <= 16, where minutes has n rows and n columns
• 1 <= minutes[i][j] <= 1000