{"problem":{"name":"Good Grid","description":{"content":"There is a grid with $N$ rows and $N$ columns of squares. Let $(i,j)$ be the square at the $i$\\-th row from the top and the $j$\\-th column from the left. These squares have to be painted in one of the","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc099_d"},"statements":[{"statement_type":"Markdown","content":"There is a grid with $N$ rows and $N$ columns of squares. Let $(i,j)$ be the square at the $i$\\-th row from the top and the $j$\\-th column from the left.\nThese squares have to be painted in one of the $C$ colors from Color $1$ to Color $C$. Initially, $(i,j)$ is painted in Color $c_{i,j}$.\nWe say the grid is a _good_ grid when the following condition is met for all $i,j,x,y$ satisfying $1 \\leq i,j,x,y \\leq N$:\n\n*   If $(i+j) \\% 3=(x+y) \\% 3$, the color of $(i,j)$ and the color of $(x,y)$ are the same.\n*   If $(i+j) \\% 3 \\neq (x+y) \\% 3$, the color of $(i,j)$ and the color of $(x,y)$ are different.\n\nHere, $X \\% Y$ represents $X$ modulo $Y$.\nWe will repaint zero or more squares so that the grid will be a good grid.\nFor a square, the _wrongness_ when the color of the square is $X$ before repainting and $Y$ after repainting, is $D_{X,Y}$.\nFind the minimum possible sum of the wrongness of all the squares.\n\n## Constraints\n\n*   $1 \\leq N \\leq 500$\n*   $3 \\leq C \\leq 30$\n*   $1 \\leq D_{i,j} \\leq 1000 (i \\neq j),D_{i,j}=0 (i=j)$\n*   $1 \\leq c_{i,j} \\leq C$\n*   All values in input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $C$\n$D_{1,1}$ $...$ $D_{1,C}$\n$:$\n$D_{C,1}$ $...$ $D_{C,C}$\n$c_{1,1}$ $...$ $c_{1,N}$\n$:$\n$c_{N,1}$ $...$ $c_{N,N}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc099_d","tags":[],"sample_group":[["2 3\n0 1 1\n1 0 1\n1 4 0\n1 2\n3 3","3\n\n*   Repaint $(1,1)$ to Color $2$. The wrongness of $(1,1)$ becomes $D_{1,2}=1$.\n*   Repaint $(1,2)$ to Color $3$. The wrongness of $(1,2)$ becomes $D_{2,3}=1$.\n*   Repaint $(2,2)$ to Color $1$. The wrongness of $(2,2)$ becomes $D_{3,1}=1$.\n\nIn this case, the sum of the wrongness of all the squares is $3$.\nNote that $D_{i,j} \\neq D_{j,i}$ is possible."],["4 3\n0 12 71\n81 0 53\n14 92 0\n1 1 2 1\n2 1 1 2\n2 2 1 3\n1 1 2 2","428"]],"created_at":"2026-03-03 11:01:14"}}