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
## Input
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
Output the value of the maximum donut in the 2D grid.
[samples]
## Scoring
Subtask 1 (13 points): $n < = 80$Subtask 2 (34 points): no further constraints
你有一栋由多个房间组成的房子，可以用一个 $n$ 行 $n$ 列的俯视平面图表示（显示房子中的墙壁和开放空间）。
你试图为房子中的每个开放空间分配一个数字。但为了防止重复，你决定：同一房间内的任意两个数字的最大公约数（GCD）必须为 1。
在这些限制下，你的任务是找出在必须为每个开放空间分配一个数字的前提下，所能分配的数字的最小可能总和。
输入的第一行包含一个正整数 $n$ $(1 \le n \le 800)$：房子的宽度和高度。
接下来的 $n$ 行，每行包含一个 $n$ 字符的字符串，表示房子的平面图。字符 "x" 表示墙壁，字符 "." 表示开放空间。
请输出一个正整数：根据上述规则，房子中所有开放空间所分配数字的最小可能总和。
完整题目：58 分
在第一个示例中，你可以在四个开放空间中放置数字 1、2、3 和 5。
## Input
输入的第一行包含一个正整数 $n$ $(1 \le n \le 800)$：房子的宽度和高度。接下来的 $n$ 行，每行包含一个 $n$ 字符的字符串，表示房子的平面图。字符 "x" 表示墙壁，字符 "." 表示开放空间。
## Output
输出一个正整数：根据上述规则，房子中所有开放空间所分配数字的最小可能总和。
[samples]
## Scoring
完整题目：58 分
## Note
在第一个示例中，你可以在四个开放空间中放置数字 1、2、3 和 5。
**Definitions**
Let $ n \in \mathbb{Z} $, $ 1 \leq n \leq 800 $, be the grid size.
Let $ G = (g_{i,j})_{i,j=1}^n $ be an $ n \times n $ grid where $ g_{i,j} = \text{`.`} $ denotes an open space and $ g_{i,j} = \text{`x`} $ denotes a wall.
Let $ S \subseteq \{1, \dots, n\} \times \{1, \dots, n\} $ be the set of coordinates of open spaces:
$$ S = \{ (i,j) \mid g_{i,j} = \text{`.`} \} $$
Let $ \mathcal{C} $ be the set of connected components of $ S $ under 4-directional adjacency (up, down, left, right); each component is a maximal connected region of open spaces.
**Constraints**
For each connected component $ C \in \mathcal{C} $, assign a positive integer $ a_{i,j} \in \mathbb{Z}^+ $ to each $ (i,j) \in C $ such that:
$$ \gcd(a_{i,j}, a_{i',j'}) = 1 \quad \forall (i,j), (i',j') \in C, \ (i,j) \neq (i',j') $$
**Objective**
Minimize the total sum:
$$ \sum_{(i,j) \in S} a_{i,j} $$