The rowers of Punt

Problem

Queen Hatshepsut sends ships to the land of Punt for incense and ivory, and on each bench two men row together. Nehesy, the leader of the expedition, knows that a pair who get along row better, and he wrote down the affinity of every pair of rowers. He wants to seat all of them in pairs so that the total affinity is as high as possible.

Write a function that takes affinity, a list of lists of whole numbers from 0 up: affinity[i][j] is the affinity between rowers i and j, equal to affinity[j][i], and affinity[i][i] is 0. The number of rowers is even, at most 10, and may be 0. Each rower sits in exactly one pair. Return a whole number: the highest sum the affinities of the pairs can reach.

With [[0, 5, 1, 2], [5, 0, 3, 1], [1, 3, 0, 4], [2, 1, 4, 0]]: pairing 0 with 1 and 2 with 3 gives 5 + 4 = 9; the other two ways give 1 + 1 = 2 and 2 + 3 = 5, so it returns 9. With two rowers, [[0, 7], [7, 0]], there is only one possible pair: 7. With no rowers, 0.

Examples

• The example

  [[0, 5, 1, 2], [5, 0, 3, 1], [1, 3, 0, 4], [2, 1, 4, 0]] → 9

• Two rowers

  [[0, 7], [7, 0]] → 7

• The pair that gets along best is not worth it

  [[0, 10, 9, 0], [10, 0, 0, 9], [9, 0, 0, 0], [0, 9, 0, 0]] → 18

Besides these, the challenge has hidden tests that are revealed when you submit your solution.

You start with this

def best_benches(affinity):
    pass

function bestBenches(affinity) {
}