# Bounding maximum sum of integer matrix entries in a non-attacking rook placement

Let $$A =(a_{ij})$$ be a $$m \times n$$ matrix with nonnegative integer entries bounded above by $$k$$. To find the set of entries of $$A$$ in a non-attacking rook placement such that the sum $$S$$ of them is maximal amounts to solving the linear assignment problem (for the matrix $$-A$$). Letting the latter maximal sum be $$S_{\text{max}}$$, I was thinking of the following question: Clearly $$S_1 = \sum\limits_{i,j}a_{ij} >S_{\text{max}}$$, however is this the best we can do, i.e. is there another inequality that gives more information somehow, i.e $$f(S_1) \geq g(S_{\text{max}})$$, for some functions $$f,g$$ (maybe even involving $$k$$)?

Because you can select at most one entry per row, $$S_\max \le \sum_i \max_j a_{ij}$$
Because you can select at most one entry per column, $$S_\max \le \sum_j \max_i a_{ij}$$
And these together imply a weak but simple bound that does not involve $$a_{ij}$$: $$S_\max \le k \min(m,n)$$