K (oK), 40 bytes

{|/+/'x./:/:(*t),'/:t:{x~?x}#+!(#x)##*x}

Try it online!

Note: Doesn't work for the first test case [[1]]

Explanation:

{ } - function with argument x

                                   #     - creata a list
                               (#x)      - with length number of rows of x
                                    #*x  - of the length of the first row
                              !          - odometer (ranged permutations)
                             +           - transpose
                            #            - filter out the rows
                      {x~?x}             - that have duplicates
                    t:                   - save it to t 
                ,'/:                     - pair up each number in each row with
            (*t)                         - a number from the first row
      x./:/:                             - index x with each of the above
   +/'                                   - find the sum of each row
 |/                                      - reduce by max