{"raw_statement":[{"iden":"statement","content":"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):\n\nNote 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.\n\nThe _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. \n\nThe first line of input contains a single positive integer $n$ ($n < = 400$): the width and height of the grid.\n\nThe next $n$ lines each contain $n$ space-separated integers, representing the elements of the grid. Each element will range from $-100$ to $100$, inclusive\n\nOutput the value of the maximum donut in the 2D grid.\n\nSubtask 1 (13 points): $n < = 80$\n\nSubtask 2 (34 points): no further constraints\n\n"},{"iden":"input","content":"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"},{"iden":"output","content":"Output the value of the maximum donut in the 2D grid."},{"iden":"scoring","content":"Subtask 1 (13 points): $n < = 80$Subtask 2 (34 points): no further constraints"},{"iden":"examples","content":"Input5\n1 3 -5 6 4\n2 5 -8 4 0\n0 8 9 3 3\n-1 5 -7 2 6\n-3 4 0 1 -1\nOutput39\nInput5\n13 15 -2 -3 -5\n14 18 -5 -8 -10\n-2 -2 1 -1 2\n4 -1 0 5 -6\n-2 -1 1 -1 0\nOutput37\nInput3\n-1 -2 -3\n-4 -5 -6\n-7 -8 -9\nOutput-40\n"}],"translated_statement":[{"iden":"statement","content":"你有一栋由多个房间组成的房子，可以用一个 $n$ 行 $n$ 列的俯视平面图表示（显示房子中的墙壁和开放空间）。 \n\n你试图为房子中的每个开放空间分配一个数字。但为了防止重复，你决定：同一房间内的任意两个数字的最大公约数（GCD）必须为 1。\n\n在这些限制下，你的任务是找出在必须为每个开放空间分配一个数字的前提下，所能分配的数字的最小可能总和。\n\n输入的第一行包含一个正整数 $n$ $(1 \\le n \\le 800)$：房子的宽度和高度。\n\n接下来的 $n$ 行，每行包含一个 $n$ 字符的字符串，表示房子的平面图。字符 \"x\" 表示墙壁，字符 \".\" 表示开放空间。\n\n请输出一个正整数：根据上述规则，房子中所有开放空间所分配数字的最小可能总和。\n\n完整题目：58 分\n\n在第一个示例中，你可以在四个开放空间中放置数字 1、2、3 和 5。"},{"iden":"input","content":"输入的第一行包含一个正整数 $n$ $(1 \\le n \\le 800)$：房子的宽度和高度。接下来的 $n$ 行，每行包含一个 $n$ 字符的字符串，表示房子的平面图。字符 \"x\" 表示墙壁，字符 \".\" 表示开放空间。"},{"iden":"output","content":"输出一个正整数：根据上述规则，房子中所有开放空间所分配数字的最小可能总和。"},{"iden":"scoring","content":"完整题目：58 分"},{"iden":"examples","content":"输入\n4\nxxxx\nx..x\nx..x\nxxxx\n输出\n11\n输入\n10\nxxxxxxxxxx\nx...x....x\nx...x....x\nx.xxxxxxxx\nxxx......x\nx.x.xxxxxx\nx.x.x....x\nxxx.xxx..x\nx.....x..x\nxxxxxxxxxx\n输出\n402\n"},{"iden":"note","content":"在第一个示例中，你可以在四个开放空间中放置数字 1、2、3 和 5。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $, $ 1 \\leq n \\leq 800 $, be the grid size.  \nLet $ 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.  \nLet $ S \\subseteq \\{1, \\dots, n\\} \\times \\{1, \\dots, n\\} $ be the set of coordinates of open spaces:  \n$$ S = \\{ (i,j) \\mid g_{i,j} = \\text{`.`} \\} $$  \nLet $ \\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.  \n\n**Constraints**  \nFor 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:  \n$$ \\gcd(a_{i,j}, a_{i',j'}) = 1 \\quad \\forall (i,j), (i',j') \\in C, \\ (i,j) \\neq (i',j') $$  \n\n**Objective**  \nMinimize the total sum:  \n$$ \\sum_{(i,j) \\in S} a_{i,j} $$","simple_statement":null,"has_page_source":false}