Since the problem asks to find the lowest possible median, we can binary search a possible value mid and check if the lowest median can be less than or equal to mid.

To check if any of the medians are $$$\leq \text{mid}$$$, consider each $$$K \times K$$$ submatrix separately. How to check if the median here is $$$\leq \text{mid}$$$? Let $$$\text{numMore}$$$ be the number of values in the submatrix that are strictly greater than $$$\text{mid}$$$. Since the median is defined as the $$$\frac{K^2}{2} + 1$$$ th highest element, we must have that $$$\text{numMore}$$$ be less than that value. It's not too hard to see why this holds; if $$$\text{numMore}$$$ is less than that value, then there will be a value $$$\leq \text{mid}$$$ in the $$$\frac{K ^ 2}{2} + 1$$$ th highest position, and if $$$\text{numMore}$$$ is more than that value, then the median will be greater than mid.

So we go through all the $$$K \times K$$$ submatrices and check whether any of the medians are $$$\leq \text{mid}$$$, and update our binary search values accordingly.

To speed up the process of finding the number of values greater than $$$\text{mid}$$$ in a submatrix, we can use prefix sums. Final complexity turns out to be $$$O(N^{2}\text{log}MAX(A_i))$$$

My code with some comments is linked here: https://atcoder.jp/contests/abc203/submissions/23086034