QOJ.ac

QOJ

Time Limit: 5 s Memory Limit: 1024 MB
Statistics

Problem Description

You are given an $r \times c$ grid. Each cell of this grid is filled with a number between $1$ and $r \times c$ inclusive, and each cell’s number is distinct.

Define a grid of numbers to be monotonic if each row and column is either increasing or decreasing (this can be different for each row or column).

Define a subgrid of the grid as follows: First choose some nonempty subset of the rows and columns. Next, take elements that lie in both the chosen rows and columns in the same order.

There are $(2^r−1)(2^c−1)$ nonempty subgrids of the given grid. Of these subgrids, count how many are monotonic.

Consider this grid:

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

There are nine $1 \times 1$ subgrids, nine $1 \times 2$’s, three $1 \times 3$’s, nine $2 \times 1$’s, nine $2 \times 2$’s, three $2 \times 3$’s, three $3 \times 1$’s, three $3 \times 2$’s, and one $3 \times 3$. They are all monotonic, for $9+9+3+9+9+3+3+3+1 = 49$ monotonic subgrids.

Input

Each test case will begin with a line with two space-separated integers $r$ and $c$ ($1 \leq r, c \leq 20$), which are the dimensions of the grid.

Each of the next $r$ lines will contain $c$ space-separated integers $x$ ($1\leq x\leq r\bullet c$, all $x$’s are unique). This is the grid.

Output

Output a single integer, which is the number of monotonic subgrids in the given grid

Samples

Sample Input 1

3 3
1 2 5
7 6 4
9 8 3

Sample Output 1

49

Sample Input 2

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

Sample Output 2

64