该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

塔尖 学院的翁老师为七月举行的夏令营制作了一张海报。

海报可以视为一个 $N\times N$ 的网格；

• 有 $K$ 种颜色，编号分别为 $1$ 到 $K$，每个格子的颜色是 $K$ 种颜色之一；
• 具体地，网格的颜色可以用一个矩阵 $A$ 来表示：
  • 记第 $i$ 行第 $j$ 列的格子为 $(i,j)(1\le i,j\le N)$，那么 $(i,j)$ 的颜色为 $A_{i,j}(1\le A_{i,j}\le K)$。

学生希望海报的颜色可以丰富一点；他们定义一张海报的 鲜艳程度 为满足以下条件的 $(i,j)(1\le i,j\le N-1)$ 的个数：

• $(i,j),(i+1,j),(i,j+1),(i+1,j+1)$ 中出现的颜色种类数不小于 $3$。

即 $A$ 中出现元素种类数不小于 $3$ 的 $2\times 2$ 子矩阵个数。

例如，下图中的海报的鲜艳程度为 $2$，因为存在 $2$ 个满足上述条件的 $2\times 2$ 子矩阵（已使用蓝框标出）。

由于时间紧迫，学生们希望通过恰好一次以下操作，或者不进行操作，来最大化海报的鲜艳程度：

• 选择恰好一个格子 $(i,j)$ 和一个与该格子原先颜色不同的颜色 $c(1\le c\le K)$，将格子 $(i,j)$ 的颜色改为 $c$，即 $A_{i,j}\gets c$。

请求出最终能得到的海报的最大鲜艳程度。

输入格式

第一行输入两个整数 $N,K$。

接下来 $N$ 行，每行输入 $N$ 个整数 $A_{i,j}$。

输出格式

输出一行一个整数，表示最终能得到的海报的最大鲜艳程度。

2 3
1 2
2 1

1

5 5
1 1 1 2 2
1 1 1 2 2
3 3 1 2 2
3 3 5 5 5
3 3 5 5 5

5

5 1000000000
104289385 946930886 881692778 914636916 257747795
524238335 819885386 849760493 696516649 389641422
225202363 550490028 883368690 302520060 344897765
267513928 565180541 740383427 404089172 503455737
135005211 621595368 394702567 926956430 436465782

16

3 3
1 2 3
2 2 2
3 2 1

2

10 11
2 2 1 3 4 3 4 3 3 5
3 2 4 3 4 4 3 3 5 5
3 4 2 2 5 5 5 5 5 5
4 2 2 3 5 3 5 5 5 6
2 2 3 5 5 5 6 6 7 5
4 4 4 5 6 4 6 7 6 6
3 3 5 4 6 6 6 5 6 8
3 3 4 4 6 5 7 7 6 8
4 4 4 6 7 5 5 8 8 7
4 4 6 5 6 6 7 6 6 9

39

提示

样例 1 解释

如下图所示，将 $(2,2)$ 的颜色改为颜色 $3$，可以使得鲜艳程度为 $1$。

可以证明不存在更优的方案。

该样例满足子任务 $1,3,4,5$ 的限制。

样例 2 解释

如下图所示，将 $(2,3)$ 的颜色改为颜色 $4$，可以使得鲜艳程度为 $5$。

可以证明不存在更优的方案。

该样例满足子任务 $3,4,5$ 的限制。

样例 3 解释

该样例满足子任务 $2,4,5$ 的限制。

样例 4 解释

该样例满足子任务 $3,4,5$ 的限制。

样例 5 解释

该样例满足子任务 $4,5$ 的限制。

数据范围

对于 $100\%$ 的数据满足：

• $2\le N\le 270$；
• $3\le K\le 10^9$；
• $1\le A_{i,j}\le K(1\le i,j\le N)$。