Non-overlapping Matrix Sum Given \$k\$ arrays of length \$n\$, output the maximum sum possible using one element from each array such that no two elements are from the same index. It is guaranteed that \$k\le n\$.
Input
A nonempty list of nonempty arrays of integers.
Output
An integer that represents the maximum sum.
Examples
Input -&gt; Output
[[1]] -&gt; 1
[[1, 3], [1, 3]] -&gt; 4
[[1, 4, 2], [5, 6, 1]] -&gt; 9
[[-2, -21],[18, 2]] -&gt; 0
[[1, 2, 3], [4, 5, 6], [7, 8, 9]] -&gt; 15
[[1, 2, 3, 4], [5, 4, 3, 2], [6, 2, 7, 1]] -&gt; 16
[[-2, -1], [-1, -2]] -&gt; -2
Jelly, 10 6 bytes

ZŒ!ÆṭṀ


Try it online!

(4 bytes saved by @Dennis, who pointed out that Jelly had a "sum of main diagonal" builtin. I was not expecting it to have one of those; the previous solution implemented the operation without using the builtin. The operation in question, Æṭ, is defined as "trace", but the trace is only defined for square matrices; Jelly implements a generalisation to rectangular matrices too.)

The improvement over the other answers is mostly from a simpler (thus terser to express) algorithm; this program was originally written in Brachylog v2 ({\p\iᶠ∋₎ᵐ+}ᶠot), but Jelly has some builtins for parts of the program that have to be spelled out in Brachylog, so this came out shorter.

Explanation

ZŒ!ÆṭṀ
Z            Swap rows and columns
 Œ!          Find all permutations of rows (thus columns of the original)
   Æṭ        {For each permutation}, take the sum of the main diagonal
     Ṁ       Take the maximum


It should be clear that for any solution to the problem, we can permute the columns of the original matrix to put that solution onto the main diagonal. So this solution simply reverses that, finding all possible main diagonals of permutations.

Note that the "permute the columns" operation is done as "transpose, permute the rows" without bothering to transpose back; the rest of the algorithm happens to be symmetrical about the main diagonal, so we don't need to undo the transpose and thus can save a byte.