AT_kupc2017_l Coin Game 2017

有一个 $H$ 行 $W$ 列的棋盘，每个格子的状态可以是以下三种之一：放置了一枚正面朝上的硬币、放置了一枚反面朝上的硬币、没有放置硬币。 同时，我们有 $H + W$ 张卡片，分别标有「第 $1$ 行」、「第 $2$ 行」……「第 $H$ 行」以及「第 $1$ 列」、「第 $2$ 列」……「第 $W$ 列」。 游戏规则如下：利用这些卡片和棋盘，两名玩家轮流进行操作，直到游戏结束。每轮操作包括以下步骤： 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 \leq W, H \leq 2,000 $ - $ m_{ij} $ 表示为 `.`, `o`, `x` 之一 - 至少存在一个反面朝上的硬币 ### 部分分数 对于符合下列额外条件的数据集，正确解答可获得 $30$ 分： - 每行至少有一个反面朝上的硬币。 - 每列至少有一个正面或者反面朝上的硬币。 不受额外条件限制的数据集正确解答可获得 $370$ 分。 ### 样例说明 1 & 2 此样例满足额外条件。 **本翻译由 AI 自动生成**