Assuming your budget is N, you need to buy a rectangular land. Give a matrix of land prices and ask what is the largest area available for buying land. Land prices must be non-negative. (Source:https://www.careercup.com/question?id=5519438609645568)

The solution provided uses a O(n^4) solution,but can this problem be solved with BFS?If we apply BFS from every point in the matrix,can we get the correct answer?

Please provide some suggestions on how to solve this question more efficiently? Thank you for your time.