AT_kupc2017_l Coin Game 2017

[problemUrl]: https://atcoder.jp/contests/kupc2017/tasks/kupc2017_l $ H $ 行 $ W $ 列に区切られた盤面があり、盤面の各マスは「表向きのコインが $ 1 $ 枚置かれている」「裏向きのコインが $ 1 $ 枚置かれている」「コインが置かれていない」のいずれかです。 また、「$ 1 $ 行目」「$ 2 $ 行目」...「$ H $ 行目」「$ 1 $ 列目」「$ 2 $ 列目」...「$ W $ 列目」と書かれたカードが $ 1 $ 枚ずつ合計 $ W\ +\ H $ 枚あります。 この盤面とこれらのカードを使い、$ 2 $ 人でゲームを行います。 ゲームは、ゲームが終了するまで手番を交互に繰り返します。 各手番は以下の手順で行います。 1. 手番プレイヤーはカードを $ 1 $ 枚自由に選んで取り除く 2. 取り除いたカードに書かれた行または列にある全てのコインの裏表を反転させる 3. 取り除くカードがなくなった場合、もしくは盤面上の全てのコインが表向きになった場合、ゲームは終了する ゲーム終了後、各プレイヤーはゲーム終了時の状態に応じて以下の点数を得ます。 - 最後にカードを取り除いたプレイヤーは $ 1 $ 点を得る - 盤面上の全てのコインが表向きになっていれば、お互いに $ 2 $ 点を追加で得る お互いに自分の得る合計点数を最大化するように最適に行動したとき、先手が得る合計点数を求めてください。

入力は以下の形式で標準入力から与えられる。 $ m_{ij} $ は $ i $ 行 $ j $ 列の状態を表しており、 `.` の場合コインが置かれていないことを、 `o` の場合表向きのコインが置かれていることを、 `x` の場合裏向きのコインが置かれていることを表す。 > $ H $ $ W $ $ m_{11} $ $ m_{12} $ $ ... $ $ m_{1W} $ $ m_{21} $ $ m_{22} $ $ ... $ $ m_{2W} $ $ : $ $ m_{H1} $ $ m_{H2} $ $ ... $ $ m_{HW} $

お互いに自分の得る合計点数を最大化するように最適に行動したとき、先手が得る合計点数を $ 1 $ 行で出力せよ。

### 制約 - $ 1\ \leq\ W,\ H\ \leq\ 2,000 $ - $ m_{ij} $ は `.`, `o`, `x` のいずれかである - 裏向きのコインが少なくとも $ 1 $ 枚置かれている ### 部分点 以下の追加制約を満たすデータセットに正解した場合は、$ 30 $ 点が与えられる。 - 各行には裏向きのコインが少なくとも $ 1 $ 枚置かれている - 各列には表向きまたは裏向きのコインが少なくとも $ 1 $ 枚置かれている 追加制約のないデータセットに正解した場合は、上記とは別に $ 370 $ 点が与えられる。 ### Sample Explanation 1 この入力例は追加制約を満たします。 ### Sample Explanation 2 この入力例は追加制約を満たします。