35350번 - ポスター 2 (Poster 2) 서브태스크다국어

JOI 学園の理恵さんは，今年 3 月に実施される文化祭のポスターを作った． このポスターは N 行 N 列のマス目の形をしており，各マスは 1 から K までの番号が付けられた K 種類の色のいずれかで塗られている． 具体的には，ポスターの上から i 行目，左から j 列目 (1 ≦ i ≦ N，1 ≦ j ≦ N) は色 A_i,j で塗られている．

しかし，このポスターについて生徒間で話し合いを行ったところ，もう少しカラフルにした方が良いのではないかという意見が出た． 具体的には，以下で定義されるカラフル度を上げた方が良いのではないかという意見が出た．

• 連続する 2 行 2 列の正方形領域のうち，3 種類以上の色を含むものの個数．

たとえば，下図左のようなポスターを作った場合，下図右に示す 2 つの長方形領域について 3 種類以上の色を含むため，カラフル度は 2 である．

ポスターの提出期限まであと数分しかないので，以下の操作を 0 回または 1 回行うことで，カラフル度を最大化したい．

• 好きなマスを 1 つ選び，そのマスの色を K 種類の色のいずれかで塗り替える．

理恵さんが最初に作ったポスターの情報が与えられるので，達成できるカラフル度の最大値を求めるプログラムを作成せよ．

入力は以下の形式で与えられる．

N K

A_1,1 A_1,2 … A_1,N

A_2,1 A_2,2 … A_2,N

︙

A_N,1 A_N,2 … A_N,N

達成できるカラフル度の最大値を 1 行で出力せよ．

• 2 ≦ N ≦ 270．
• 3 ≦ K ≦ 10⁹．
• 1 ≦ A_i,j ≦ K (1 ≦ i ≦ N，1 ≦ j ≦ N)．
• 入力される値はすべて整数である．