操作の途中で複数の駒が同じマスに存在してもよいことにします． 最終状態において各マスに \(1\) つ以下の駒しかないならば，この緩和をしても答えは変わりません．

まずは \(M\) が偶数の場合で \(f(1,N)\) を求めます．

初期状態で奇数個の駒が置いてある行を \(r_1,r_2,\ldots,r_k\) とします． \(k\) が奇数の場合，全行の駒の個数を偶数にすることはできないので，\(f(1,N)=0\) です．

\(k\) が偶数のときを考えます． \(f(1,N)\) の下界として，\((r_2-r_1)+(r_4-r_3)+\cdots+(r_{k}-r_{k-1})\) という値が考えられます． ただし，これでは十分でないケースがあります． 例えば以下です．

O...  (r_1)
O..O
O.O.
O...  (r_2)

この例では \(3\) 回の操作では足りず，\(4\) 回の操作が必要です． 一般に．奇数行ペア \((l,r)\) の間で以下の条件が成立するとき，\(l,r\) をペアにする最小コストが \(r-l+1\) になります．

• \(S_l=S_r\)
• すべての \(l<i<r\) に対し，\(S_l\) と \(S_i\) はちょうど \(1\) 列だけ異なる．

証明は帰納法でできます．

以下，\(cost(l,r)\) を，奇数行 \(l,r\) をペアにするときのコストとします． このとき，\(f(1,N)=\sum_{i=1,3,\ldots,k-1} cost(r_i,r_{i+1})\) と計算できます． つまり，奇数行を順番にペアにするのがそのまま最適解であるということです．

これは以下の方針で証明できます．例えば今，\(4\) つの奇数行 \(a<b<c<d\) があるとします．順番通り \((a,b),(c,d)\) とペア分けした場合，コストは高々 \((b-a)+(d-c)+2\) です． 一方，順番通りペア分けしない解を考えると，コストは最低でも \((c-a)+(d-b)\) 必要で，これは \((b-a)+(d-c)+2\) 以上です． よって順番通りにペア分けして損しないことが分かります． このような議論を一般の場合でも行うことができ，最適解の構造が奇数行を順番にペアにする形であることが示せます．

この構造が分かると，\(\sum f(L,R)\) を計算するのも簡単です． \(L\) 行目以前にあった奇数行の数の偶奇を \(2\) 通り考え，各パターンに対し，各奇数行ペアの寄与を独立に計算することができます． 計算量は \(O(NM)\) です．

次に，\(M\) が奇数の場合を考えます． まずは \(f(1,N)\) を求めます．

まず，\(M\) 個駒が置かれている行がない場合を考えます． すると，\(M\) が偶数の時と全く同様に解くことができるとわかります．

では，\(M\) 個駒が置かれている行がある場合はどうすればよいでしょうか？ まず，解は以下のような構造をしていると限定しても問題ありません．

• Step 1: \(M\) 個駒が置かれている行がある限り，そのような行の駒を選んで操作する．
• Step 2: \(M\) 個駒が置かれている行がなくなったら，最適手順が計算できるので，それに従う．

ここで，初期状態において行 \(i\) に置かれている駒の個数を \(c_i\)，最適解の Step 1 終了後において行 \(i\) に置かれている駒の個数を \(d_i\) とします．

ここで \(c_i\), \(d_i\) に対して以下の性質が確認できます．

• \(c_i=M\) なら \(d_i=M-1\) である．
• \(c_i \leq M-1\) なら，\(c_i \leq d_i \leq M-1\) である．
• \(e_i=c_i-d_i\) という値を考える．\(e_i\) のプラス部分と \(e_i\) のマイナス部分を順にマッチさせることを考える． 例えば，\(e=(+1,0,-2,+1)\) なら，\(1 \to 3\), \(4 \to 3\) という風にマッチさせる．（プラス側 \(\to\) マイナス側という順番で書く）
• \(u \to v\) (\(u<v\)) というマッチがある場合，\(d_u,d_{u+1},\ldots,d_{v-1}\) はすべて \(M-1\) である．
• \(u \to v\) (\(u>v\)) というマッチがある場合，\(d_u,d_{u-1},\ldots,d_{v+1}\) はすべて \(M-1\) である．

ここで．\(d_i\) が与えられたときに，それに対応する最小の移動回数を求めることを考えます． まず，行移動の回数を最小化するのは簡単です． \(e_i\) のプラスマイナスを順にマッチさせたあと，\(d_i\) の奇数行同士をまた順にマッチさせればよいです． この時の列移動の回数はいくらになるでしょうか？ まず，\(d_i\) の奇数行ペア \(l,r\) であって，以下のような条件を満たすようなもの \(1\) つごとに，追加で \(1\) 回の列移動が必要です．

• \(e_i\) のマッチによる行移動が，区間 \([l,r]\) (端点含む) に一切関与しない．
• \(S_l=S_r\)
• 各 \(l<i<r\) に対し，\(S_i\) と \(S_l\) はちょうど \(1\) 列だけ異なる

逆に，これ以外の奇数ペアでは追加の列移動を \(0\) 回に抑えることができます． これをきちんと確認しましょう． まず，\(e_i\) のマッチによって行 \(z,z+1\) 間の移動が起きているとき，行 \(z,z+1\) が連結であると言うことにします．

ある連結成分に注目してみます． この連結成分が行の区間 \([L,R]\) であるとします． この連結成分内でのマッチ \(u\to v\) は，すべて \(u<v\) の向きであるか，すべて \(u>v\) の向きであるかのいずれかです． \(u<v\) だとして考えてみましょう（\(u>v\) のケースも同様です）．

ここで，\(u \to v\) という操作をするとき，\(u\) 行目は \(M\) 列全部埋まっている状態なので，\(v\) 行目の空きマスのうち好きな列を選んで移動を行うことができます．ここで，\(R\) 自身が奇数行である場合は，\(R\) 行目の状態を \(2\) 通り以上から選べることになるので，\(R\) 行目の関係する列移動は回避できます．

では \(R\) が偶数行で別の奇数行に挟まれている場合はどうなるかという話になりますが，実はこのようなケースはありません．というのも，\(R\) が偶数行で別の奇数行に挟まれている場合，\([L,R]\) 成分の最後のマッチ \(u \to R\) を削除して，\([L,R]\) を挟む奇数行 \(p,q\) に対し，\((p,u),(R,q)\) という形で組みなおすことで，よりよい解が得られるからです．これは \(d_i\) を最適解から取り出してきたという前提に矛盾します．

今の観察を整理すると，最適解は以下のような手順で得られるとわかります．

• 各奇数行を順番にペアにする．
• \(c'_i\) を \(c_i\) 以下の最大の偶数とすると，行 \(i\) は \((M-1-c'_i)/2\) 個のペアを受け入れる余裕がある．
• ペアを，余裕のある行へと移動させていく．
• 奇数行ペア \((l,r)\) が以下の条件をすべて満たすときのみ，追加で列移動コスト \(+1\) がかかる．
  • ペア \((l,r)\) はこの内部にある行に吸収される．
  • \([l,r]\) 内に外側からペアが来ない
  • \([l,r]\) だけ見たとき，\(l,r\) ペアでは列移動が必要になる

この考察をもとに，問題を以下のような直線上のマッチング問題に帰着します．

• 各行 \(i\) について，\((m-1-c'_i)/2\) 個の 穴 が座標 \(i\) にあると考える．
• 奇数行を順に \(l_1,r_1,l_2,r_2,\ldots\) とする．各 \((l_i,r_i)\) に対し，まず \(r_i-l_i\) を答えに加算する．そして，区間 \([l_i,r_i]\) の中の自由な座標にボールを置く．
• ボールを移動させて，穴に入れる．各穴には \(1\) つ以下のボールが入る．ボールを移動させた距離の総和を \(X\) とすると，答えに \(2X\) を加算する．
• \([l_i,r_i]\) 内に穴が存在しており（つまり \(l_i\) 行目から \(r_i\) 行目だけを見たときに奇数行を消すことができ），かつこの中で奇数行を消すコストが \(r_i-l_i+1\) になる（つまり \(l_i,r_i\) 行目は等しく，その間の行はちょうど \(1\) 列ずつ異なる）とき，\((l_i,r_i)\) を bad なペアと呼ぶことにする．
• 各 bad ペア \((l_i,r_i)\) について，\([l_i,r_i]\) 内の穴に \((l_i,r_i)\) 由来でないボールが来ているなら，bad ペア由来の余計な列移動が発生しないようにできる．逆に，\([l_i,r_i]\) 内の穴に外側からボールが来ていない（そして \([l_i,r_i]\) 内で \((l_i,r_i)\) のボールを消費する）ときは，追加で \(1\) のコストがかかる．

ここで，最終的な答えを最小化する際，まず \(X\) を最小化してよいことが今までと同じような議論で証明できます．

あとは，\(X\) を最小化する割り当ての中でさらに bad 由来のコストを最小化する方法を考えます．

見通しをよくするために，問題を以下の形にさらに変形します．

• それぞれのボールと穴に，座標ではなく，座標の区間を割り当てることにする．
• ペア \((l_i,r_i)\) に対し，\([l_i,r_i]\) 内に穴が存在しない場合は，\([l_i,r_i]\) を割り当てたボールを用意する．
• ペア \((l_i,r_i)\) に対し，\([l_i,r_i]\) 内に穴が存在する場合，穴の座標を \(x_i\) (\(l_i \leq x_1 \leq x_2 \leq \cdots \leq x_k \leq r_i\)) とする．そして，\([l_i,l_i]\) を割り当てたボールと \([r_i,r_i]\) を割り当てたボールを用意する．さらに，\([l_i,x_1], [x_1,x_2],\ldots,[x_k,r_i]\) を割り当てた穴を用意する．
• 奇数行ペアに挟まれていない行 \(i\) にある穴には \([i,i]\) を割り当てておく．

こうして得られた区間たちは，互いに交差しないことがわかります． つまり，\(2\) つの区間 \([a,b],[c,d]\) があった場合，\(b \leq c\) もしくは \(d \leq a\) が成立します． こうして得られた穴とボールのマッチング問題を考えます． \(2\) つの区間をマッチさせるコストは，その区間の間の距離です． すべてのボールをマッチさせる最小コストを考えると，元問題での最小マッチングと等しいことが分かります． また bad ペアの処理は，ある連続する穴たちを一つも利用しない場合はペナルティでコスト\(+1\)，という形で書けます．

一つ例を挙げます．以下のような入力を考えます．

O..
OO.
...
O..
OOO
OO.
OOO
OOO
...
OOO

これに対しては，以下のようなボールと穴が生成されます．

ボール [1,1], 穴 [1,1], 穴 [1,3], 穴 [3,4], 穴 [4,4], ボール [4,4], ボール [5,7], ボール [8,8], 穴 [8,9], 穴 [9,10], ボール [10,10]

そして，穴 \([1,3]\), 穴 \([3,4]\) を両方使わない場合に限り，bad ペア由来のコスト \(+1\) が発生します．

では具体的に \(X\) を求める方法を考えましょう． 穴とボールを座標順にソート（区間が交差しないことから順序が自然に定まっている）します． 穴に \(+1\)，ボールに \(-1\) を割り当てて，その累積和を高さとして考えます．

最適解では，同じ高さの穴とボールをマッチングさせると考えてよいです．

上の例を使うと，以下のようになります．

                            +[4,4] -[4,4]
                     +[3,4]               -[5,7]               +[9,10] -[10,10]
              +[1,3]                             -[8,8] +[8,9]
-[1,1] +[1,1]

まず高さごとに独立に最適なマッチングを考えます． ある高さに注目したとき，\(-\) の個数と \(+\) の個数がどうなっているかに注目します． \(-\) の個数が多い場合，そもそも解が存在しないことになります． 個数が等しい場合，マッチングは一意に定まります． \(+\) の個数が多い場合，\(1\) つだけ捨てる \(+\) があるので，これを全部試して最小のコストを計算すればよいです．

bad ペアのコスト計算はどうすればよいでしょうか？ まず，各高さに対して最小コストを求める際，未使用にする可能性のある \(+\) 区間が求まります． これらの \(+\)区間を，削除候補区間と呼ぶことにします．

各 bad ペアにはいくつかの \(+\) 区間が対応しています． これらの区間がすべて削除候補区間である場合が重要です． この中で \(1\) つでも削除しない区間があればコストの増加を避けられることになります． では，コストの増加を避けられないケースとは，どのような状況でしょうか？

bad ペアの列 \(b_1,b_2,\ldots,b_k\) であって，以下のような条件を満たすものを bad ペア鎖と呼ぶことにします．

• 各 \(b_i\) に対応する \(+\) 区間を \(c_{i,1},c_{i,2},\ldots,c_{i,s_i}\) とする．
• \(c_{i,1}\) と同じ高さで左にある \(+\) 区間 \(d\) であって，削除したときのコストが \(c_{i,1}\) 以下のものは存在しない．
• \(c_{i,s_i}\) と \(c_{i+1,1}\) は，削除したときのコストが等しい．また，これらと同じ高さでこれらの間にある区間 \(d\) であって，削除したときのコストが \(c_{i,s_i},c_{i+1,1}\) 以下のものは存在しない．
• \(c_{k,s_k}\) と同じ高さで右にある \(+\) 区間 \(d\) であって，削除したときのコストが \(c_{k,s_k}\) 以下のものは存在しない．

この bad ペア鎖が \(1\) つあるごとに，コストが \(+1\) されることになります． いずれかのペアでコスト \(+1\) を受け入れる代わりにほかのペアでのコスト増加を避けられるのは明らかです． 論証が必要なのは，鎖 \(1\) つごとにコスト \(+1\) が避けられないことです． より具体的に言えば，以下の事実の確認が必要です．

• \(c_{i,1}\) の高さを \(H_L\)，\(c_{k,s_k}\) の高さを \(H_R\) とする． 高さ \(H_L\) 以上 \(H_R\) 以下の削除候補区間をすべて集めると，ちょうど \(c_{i,j}\) たちと一致する．

これは次のように証明できます． まず，削除候補区間に対して，以下の性質が成り立ちます．

• 高さ \(h\) の削除候補区間のうち最も右のものを \(p\)，高さ \(h+1\) の削除候補区間のうち最も左のものを \(q\) とすると，\(p\) は \(q\) より必ず左にある

これはつまり，削除候補区間は高さに応じて単調に右にずれていくことを主張しています． これは各段でのコストの計算式を丁寧に分解することでも示せますし，また，全体最適となる解の構造を考えることでも示せます．

この性質を用いると，bad ペア鎖の中にある \(c_{i,j}\) たちはすべて削除候補区間であり，かつそれ以外の削除候補区間がないことが分かります．

ここまでの議論を踏まえれば，\(f(1,N)\) を計算するのは簡単です． そして，\(f(L,R)\) の計算も難しくありません． 以下のように分解して考えればよいです．

• \(+\) と \(-\) の個数が等しい高さの寄与: ある \(+,-\) ペアが利用できる条件は，\(L\) に対応する点と \(R\) に対応する点との相対位置の条件で書ける．平面走査 + Segment Tree で処理すれば，全部合わせて \(O(N \log N)\) 時間で計算できる．

• \(+\) と \(-\) の個数が等しい高さの \(X\) への寄与: \(2\) つの \(+\) 区間 \(p,q\) があったとき，これらの削除コストの差分がどうなるか考えると，これは \(p,q\) の間にある区間のみで決まっている．これを式で書くと，結局，\(L,R\) が固定されたときに消すべき \(+\) 区間はとある数列の区間 argmin を計算することで求まる．よって Cartesian Tree を利用することによって全 \(L,R\) に対するコストの総和を計算できる．計算量は全体 \(O(N)\) になる．

• bad ペア由来の寄与: bad ペアチェインの個数を DP で求めればいい．条件は，始点，隣接ペア，終点と分解してかけるので，素直に DP できる．全体で \(O(N)\) 時間で計算できる．

以上をすべて実装すれば，全体で \(O(NM+N \log N)\) 時間の解法が得られます．

解答例(C++)