题目描述

现有一个 $n$ 行 $m$ 列的网格，行按从上到下的顺序从 $1$ 到 $n$ 编号，列按从左到右的顺序从 $1$ 到 $m$ 编号。第 $i$ 行第 $j$ 列的单元格权值为 $w_{i,j}$。

现在你可以用任意多个（包括零个）$1 \times k$ 的骨牌覆盖这个网格，骨牌可以旋转，$k$ 可以取任意正整数，但不能超出网格边界，每个骨牌选取的 $k$ 可以不同。覆盖时需保证这些骨牌不重叠，且没有边相邻。求覆盖的格子权值和最大为多少。

输入格式

第一行两个整数 $n, m$ （$1 \leq n, m \leq 18$），表示网格大小。

接下来 $n$ 行，第 $i$ 行 $m$ 个整数 $w_{i,1}, w_{i,2}, \ldots, w_{i,m}$ （$|w_{i,j}| \leq 10^6$），表示单元格的权值。

输出格式

输出一行一个整数，表示覆盖的格子权值和的最大值。

2 2
2 1
1 1

3

4 4
-1 2 1 -2
3 2 0 -2
-3 -2 0 3
2 3 0 1

15