{"problem":{"name":"Adjacent Difference","description":{"content":"There is a grid with $N$ rows and $N$ columns. Let $(i, j)$ denote the cell at the $i$\\-th row from the top and the $j$\\-th column from the left. Each cell contains an integer. Initially, cell $(i,j)$","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc066_a"},"statements":[{"statement_type":"Markdown","content":"There is a grid with $N$ rows and $N$ columns. Let $(i, j)$ denote the cell at the $i$\\-th row from the top and the $j$\\-th column from the left.\nEach cell contains an integer. Initially, cell $(i,j)$ contains the integer $A_{i,j}$.\nYou can repeatedly perform the following operation:\n\n*   Choose integers $i$ and $j$ such that $1\\leq i, j\\leq N$ and an integer $x$, and add $x$ to $A_{i,j}$. The cost of this operation is $|x|$.\n\nYou are given a positive integer $d$. Your goal is to satisfy the following condition:\n\n*   The difference between the integers written in any two cells that are vertically or horizontally adjacent is at least $d$. More formally, the following two conditions are satisfied:\n    *   $|A_{i,j}-A_{i+1,j}|\\geq d$ for all integers $i$ and $j$ such that $1\\leq i\\leq N-1$ and $1\\leq j\\leq N$.\n    *   $|A_{i,j}-A_{i,j+1}|\\geq d$ for all integers $i$ and $j$ such that $1\\leq i\\leq N$ and $1\\leq j\\leq N-1$.\n\nAchieve this goal with a total cost of $\\frac12 dN^2$ or less.\n\n## Constraints\n\n*   $2\\leq N\\leq 500$\n*   $1\\leq d\\leq 1000$\n*   $-1000\\leq A_{i,j}\\leq 1000$\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$ $d$\n$A_{1,1}$ $\\cdots$ $A_{1,N}$\n$\\vdots$\n$A_{N,1}$ $\\cdots$ $A_{N,N}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc066_a","tags":[],"sample_group":[["3 5\n-2 1 3\n3 -4 -4\n0 1 3","\\-2 8 3\n3 -9 -4\n-2 8 3\n\nPerform the operation four times as follows to yield the grid shown in the sample output:\n\n*   Perform the operation with $(i,j,x)=(1,2,7)$.\n*   Perform the operation with $(i,j,x)=(2,2,-5)$.\n*   Perform the operation with $(i,j,x)=(3,1,-2)$.\n*   Perform the operation with $(i,j,x)=(3,2,7)$.\n\nThe total cost is $7+5+2+7=21$, which is not greater than $\\frac{1}{2}dN^2=\\frac{45}{2}$."],["5 2\n1 5 5 0 3\n2 0 2 5 1\n5 2 0 5 5\n3 7 2 0 1\n6 0 4 3 6","0 4 6 1 3\n3 1 3 6 1\n5 3 0 3 5\n2 6 3 1 3\n4 0 5 3 6"]],"created_at":"2026-03-03 11:01:14"}}