Let $\circ$ denote the Hadamard product, $A\circ B=(a _{ij} b _{ij}) _{1\le i,j\le n}$, and let $f(A)$ denote the sum of the entries of $A$. Each good set corresponds to a permutation in $S _n$. Let our matrix be $C$, then we are given that there are $k$ permutation matrices $P _{\sigma_i}$, $\sigma _i\in S _n$, such that $f(P _{\sigma _i}\circ C)=M$, and $\sum P _{\sigma _i}$ has all entries $\geq 1$.
Let $\pi\in S_n$ be so that, $M _{0}=f(P _{\pi}\circ C) < M$, then we look at $\sum P _{\sigma _i}-P _{\pi}$, it has nonnegative entries and equal sums of rows and columns. Such a matrix can be written as a sum $\sum P _{\tau _i}$, $\tau _i\in S_n$, this is a simple exercise in combinatorics (maybe you have heard it in the form, every bipartite regular multigraph can be written as a union of perfect matchings). So we have
$$kM-M _{0}=f\left((\sum P _{\sigma _i}-P _{\pi})\circ C\right)=f\left((\sum P _{\tau _i})\circ C\right)=\sum f(P _{\tau _i}\circ C)\le (k-1)M$$
which gives us a contradiction. So $f(P _{\pi}\circ C)=M$, but $\pi$ was arbitrary, so we are done.
