407563: GYM102829 J Island Grid

Often, UTPC problem writers struggle to make the problem that they come up with match the particular theme of the week. For example, here is a problem that the UTPC officers found hard to fit inside this week's meta theme. You are given a 2D grid of numbers and want to find the highest value island that you can create out of this grid. You can create an island by picking an initial starting coordinate and taking all grid spaces such that there exists a path taking only cardinal directions with grid values that are only greater than or equal to the grid value at the initial starting coordinate. The value of the island is the grid value at the initial starting coordinate multiplied by the number of grid entries that the island covers. Can you find the maximum value island on the grid? If there are multiple islands with equal value, always take the one that covers more grid entries.

The first line of the input will consist of a single integer $$$n$$$ ($$$1 \leq n \leq 500$$$). The next $$$n$$$ lines of input will each consist of $$$n$$$ integers, $$$a_{ij}$$$ ($$$1 \leq a_{ij} \leq 10^9$$$).

Output two space-separated integers, the maximum value of an island you can create and the size of the associated island.

3
1 1 1
1 10 1
1 1 1

10 1

3
1 1 1
1 9 1
1 1 1

9 9

For the first test case, it is optimal to take the $$$10$$$ spot only. For the second test case, it is optimal to take the entire grid.