AT_abc407_g [ABC407G] Domino Covering SUM
题目描述
给你一个 $H$ 行 $W$ 列的网格，第 $i$ 行第 $j$ 列的格子上写有数字 $A_{i,j}$。
你要在网格上摆放若干个多米诺骨牌，每个骨牌盖住相邻的两个格子。你要保证没有任何一个格子被多于一个骨牌盖住。
求摆放完骨牌之后，所有**没有**被骨牌盖住的格子上的数字之和的最大值。
输入格式
第一行两个整数 $H,W(H,W\ge 1,H\times W\le 2000)$。\
接下来 $H$ 行，每行 $W$ 个整数表示 $A(-10^{12}\le A_{i,j}\le 10^{12})$。
输出格式
一行一个整数表示答案。
说明/提示
**样例解释 1**
网格如下所示：
以下的摆放方式中未被盖住的数字之和为 $23$。
可以证明此值无法达到 $24$ 或更大，故输出 $23$。
By @[chenxi2009](/user/1020063)