407779: GYM102892 8 Maximum Donut

You have an $$$n$$$ by $$$n$$$ 2D grid of integers ranging from $$$-100$$$ to $$$100$$$. You define a donut as a ring of numbers in the 2D grid, with a width of one. For example, this is an example of a donut (highlighted in green):

Note that a donut must include a "hole", i.e. a $$$2$$$x$$$2$$$ square is not considered a donut. Note also that a donut does not have to be in a square shape.

The value of a donut is defined as the sum of the numbers that it contains. For example, the donut pictured above has a value of 27. Given an $$$n$$$ by $$$n$$$ 2D grid, your task is to find the donut with the maximum value.

The first line of input contains a single positive integer $$$n$$$ ($$$n <= 400$$$): the width and height of the grid.

The next $$$n$$$ lines each contain $$$n$$$ space-separated integers, representing the elements of the grid. Each element will range from $$$-100$$$ to $$$100$$$, inclusive

Output the value of the maximum donut in the 2D grid.

Subtask 1 (13 points): $$$n <= 80$$$

Subtask 2 (34 points): no further constraints

5
1 3 -5 6 4
2 5 -8 4 0
0 8 9 3 3
-1 5 -7 2 6
-3 4 0 1 -1

39

5
13 15 -2 -3 -5
14 18 -5 -8 -10
-2 -2 1 -1 2
4 -1 0 5 -6
-2 -1 1 -1 0

37

3
-1 -2 -3
-4 -5 -6
-7 -8 -9

-40