题目描述

给定一个 $r \times c$ 的网格。网格的每个格子都填有一个 $1$ 到 $r \cdot c$ 之间的整数，且所有格子中的数互不相同。

如果一个网格的每一行和每一列都是单调递增或单调递减的（不同行或不同列的单调方向可以不同），则称该网格为 单调网格。

按下述方式定义网格的一个 子网格：首先选择若干行和若干列（均非空）。然后，取出这些选定行和选定列所对应的元素，并保持原有的顺序。

给定网格共有 $(2^r - 1)(2^c - 1)$ 个非空子网格。请统计其中有多少个子网格是单调的。

考虑如下网格：

$$\begin{array}{} 1 & 2 & 5\\ 7 & 6 & 4\\ 9 & 8 & 3 \end{array}$$

它有 9 个 $1 \times 1$ 子网格、9 个 $1 \times 2$ 子网格、3 个 $1 \times 3$ 子网格、9 个 $2 \times 1$ 子网格、9 个 $2 \times 2$ 子网格、3 个 $2 \times 3$ 子网格、3 个 $3 \times 1$ 子网格、3 个 $3 \times 2$ 子网格和 1 个 $3 \times 3$ 子网格。所有这些子网格都是单调的，因此单调子网格的总数为 $9 + 9 + 3 + 9 + 9 + 3 + 3 + 3 + 1 = 49$。

输入格式

每个测试用例的第一行包含两个空格分隔的整数 $r$ 和 $c$（$1 \leq r, c \leq 20$），表示网格的尺寸。

接下来的 $r$ 行，每行包含 $c$ 个空格分隔的整数 $x$（$1 \leq x \leq r \cdot c$，所有 $x$ 互不相同），表示网格。

输出格式

输出一个整数，表示给定网格中单调子网格的数量。

3 3
1 2 5
7 6 4
9 8 3

49

4 3
8 2 5
12 9 6
3 1 10
11 7 4

64

提示

翻译由 DeepSeek V3.2 完成