Colorful Quadrants

문제

You are given an $n\times nn\; \backslash times\; n$ grid, and some of the grid points are colored by one of the $kk$ colors. The color of a point is represented by an integer from $00$ to $kk$, where $00$ represents the uncolored case. Note that multiple points may be colored the same. The rows and columns of the grid are denoted by integers from $11$ to $nn$, and a point located at row $ii$ and column $jj$ is denoted by $(i,j)(i,j)$. For an uncolored point $(i,j)(i,j)$ that satisfies and , we define four sub-grids by removing row $ii$ and column $jj$ from the grid. Each of the four sub-grids is called NW (northwest), NE (northeast), SW (southwest), and SE (southeast) based on the position relative to $(i,j)(i,j)$. We say that $(i,j)(i,j)$ has colorful quadrants if, when selecting one point from each of the four sub-grids, the chosen four points are all of different colors.

See Figure C.1(a) as a $5\times 55\; \backslash times\; 5$ grid example. The point $(2,3)(2,3)$ has colorful quadrants because NW has color $11$, NE has color $44$, SW has color $33$, and SE has color $22$, as shown in Figure C.1(b). However, the point $(4,3)(4,3)$ does not have colorful quadrants because both SW and SE have color $22$ only, as shown in Figure C.1(c).

Figure C.1

Given an $n\times nn\; \backslash times\; n$ grid containing at least four grid points colored in different colors, write a program to count the number of uncolored points that have colorful quadrants.

입력

Your program is to read from standard input. The input starts with a line containing two integers, $nn$ and $kk$ (3 ≤ n ≤ 2\,000, 4 ≤ k ≤ 1\,000), where $nn$ is the number of rows and columns of the grid and $kk$ is the number of colors. In the following $nn$ lines, the $ii$-th line contains $nn$ integers that represent the colors of the points $(i,j)(i,j)$ for 1 ≤ j ≤ n. The integer $cc$ that represents the color of a point is in range 0 ≤ c ≤ k.

출력

Your program is to write to standard output. Print exactly one line. The line should contain the number of uncolored points that have colorful quadrants.

5 4
0 1 0 0 4
2 0 0 1 3
3 0 2 0 0
0 0 0 0 0
0 2 1 2 0

1

3 4
1 2 3
4 1 2
3 4 1

0

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

0