Colorful Quadrants

You are given an $n \times n$ grid. Some of its points are colored with one of $k$ colors. The color of a point is an integer from $0$ to $k$, where $0$ means the point is uncolored. Several points may share the same color. Rows and columns are numbered from $1$ to $n$, and the point in row $i$ and column $j$ is written $(i,j)$.

For an uncolored point $(i,j)$ with $1 < i < n$ and $1 < j < n$, remove row $i$ and column $j$ from the grid. This leaves four sub-grids, called NW (northwest), NE (northeast), SW (southwest), and SE (southeast) according to their position relative to $(i,j)$. The point $(i,j)$ has colorful quadrants if you can choose one point from each of the four sub-grids so that the four chosen points all have different colors.

Figure C.1

See Figure C.1(a) for a $5 \times 5$ grid. The point $(2,3)$ has colorful quadrants: NW has color $1$, NE has color $4$, SW has color $3$, and SE has color $2$ (Figure C.1(b)). The point $(4,3)$ does not, because SW and SE both contain only color $2$ (Figure C.1(c)).

Given an $n \times n$ grid that contains at least four colored points with different colors, count the number of uncolored points that have colorful quadrants.

The first line contains two integers $n$ and $k$ ($3 \le n \le 2\,000$, $4 \le k \le 1\,000$), where $n$ is the number of rows and columns of the grid and $k$ is the number of colors. Each of the next $n$ lines contains $n$ integers. The $j$-th integer on the $i$-th line is the color $c$ of point $(i,j)$, where $0 \le c \le k$.

Print one line containing the number of uncolored points that have colorful quadrants.