Median Rearrangement

You have an $n \times n$ matrix $a$. You can rearrange the elements of the matrix in any way. Let $m_1, m_2, \dots, m_n$ be the medians of each row in $a$ after the rearrangement. The goodness of the matrix $a$ is defined as the minimum median among the medians of all rows i.e $\min(m_1, m_2, \dots, m_n)$. Naturally, rearranging values also comes with a cost. The cost of rearrangement is defined a