マス \((1,1)\) に着目すると、少なくとも一回 \(L\) と \(U\) から要素を選んで操作をする必要があることが分かります。

マス \((1,N),(N,1),(N,N)\) についても同様の議論をすると、\(U,D,L,R\) からそれぞれ \(2\) 要素を選ぶ必要があります。

選んだ要素を \(U_{u1},U_{u2}, D_{d1},D_{d2},L_{l1},L_{l2},R_{r1},R_{r2}\) とします。\((u1<u2,d1<d2,l1<l2,r1<r2)\)

まず、操作は \(U_{u2}\) と \(L_{l2}\) を選んで行うとして良いです。（UR,RD,DL についても同様）なぜならば、そうでないとき操作対象を入れ替えて損しないからです。

塗られる \(4\) つの領域の和集合を考えると、覆えない場合は \(u2+1<d1\) かつ \( r2+1<l1\) のとき、または \(d2+1<u1\) かつ \(l2+1<r1\) のときに限られ、それ以外の場合は全てを覆えることがわかります。

\(4\) 回の操作では全てを覆えず、\(5\) 回操作を行う場合について考えます。

先ほどの議論と同様に操作の入れ替えを考えると、\(U\) と \(L\) を組とする操作を \(2\) 回以上行う必要がないこと、\(U\) 同士を組とする操作も行う必要がないことがわかります。

上の議論から、\(5\) 回目の操作としては \(U\) と \(D\) を組とするか、\(L\) と \(R\) を組とするのみを考えれば良いです。

\(U\) と \(D\) を組とする場合に覆えることを証明します。（\(R\) と \(L\) を組とする場合の証明も同様）

上の選んだ要素を \(U_{u1},U_{u2},U_{u3}\)、下の選んだ要素を \(D_{d1},D_{d2},D_{d3}\) とインデックスを付け直します。

このとき、\((U_{u1},D_{d3}), (U_{u2},R_{r2}),(U_{u3},L_{l2}),(D_{d1},R_{r1}),(D_{d2},L_{l1})\) の組み合わせで操作を行うと、全体を覆うことができます。

以上の議論より、\(6\) 回以上の操作が不要なこともわかります。

ここまでで最適解の構造がわかりました。

\(5\) 回操作を行う時の最小コストを求めるのは容易です。

\(4\) 回操作を行う時の最小コストを求めるには様々な方針が考えられますが、\(u2+1<d1\) を満たす/満たさないときの最小コストが計算できるので、それを用いることで \(4\) 回で全体を覆う場合の最小コストも計算できます。

Bonus:角のマスにも整数が書いてある場合を解きましょう(1000点程度？)