The Volunteer Rota

A community kitchen has n volunteers and n shifts, and every volunteer takes exactly one shift. cost[i][j] is how inconvenient shift j is for volunteer i (a number from 0 to 99), or -1 if volunteer i cannot work shift j at all.

Write cheapest_rota(cost) that returns the smallest possible total inconvenience of a rota in which every volunteer has a different shift they can work. Return -1 if no such rota exists.

With 16 volunteers there are more than 20 trillion ways to hand out the shifts, so trying them all is out of the question.

The larger tests build their tables with shift_costs(n, seed, blocked), which is available in your code: it returns an n × n table in which roughly the share blocked of the entries are -1.

Examples

Input:  cost = [[4, 1, 3],
                [2, 0, 5],
                [3, 2, 2]]
Output: 5
Explanation: volunteer 0 takes shift 1 (1), volunteer 1 shift 0 (2), volunteer 2 shift 2 (2).

Input:  cost = [[-1, 7],
                [-1, 3]]
Output: -1
Explanation: nobody can work shift 0.

Input:  cost = [[8]]
Output: 8

Constraints

• 1 <= n <= 16, cost is an n × n list of lists
• every entry is -1 or an integer from 0 to 99

Goals

• Recognise when trying every permutation is hopeless
• Replace the order of choices by the set of choices already made
• Store a DP table indexed by a bitmask