Monotony

Time limit5sMemory limit512 MB

Summary

Count the subgrids where every row and every column is strictly increasing or strictly decreasing, in a grid of distinct values up to 20 by 20.

Level: Hard8 of 10
Topics: Matrix, Dynamic programming, Combinatorics
Solved: No attempts yet

Problem

The grid has $r$ rows and $c$ columns. Each cell holds an integer between 1 and $r \times c$ inclusive, and every cell's number is distinct.

A grid is monotonic if each row and each column is either increasing or decreasing. Each row and each column may have its own direction.

To form a subgrid, first choose a nonempty subset of the rows and a nonempty subset of the columns. Then take the cells where the chosen rows and columns meet, keeping their original order.

The grid has $(2r-1)(2c-1)$ nonempty subgrids. Count how many of them are monotonic.

Consider this grid:

1 2 5
7 6 4
9 8 3

It has nine 1×1 subgrids, nine 1×2, three 1×3, nine 2×1, nine 2×2, three 2×3, three 3×1, three 3×2, and one 3×3. All of them are monotonic, so the count is 49.

Input

Each test case starts with a line containing two space-separated integers $r$ and $c$ ( $1 \le r, c \le 20$ ). Each of the next $r$ lines contains $c$ space-separated integers $x$ ( $1 \le x \le r \times c$ , all $x$ are distinct). This is the grid.

Output

Print a single integer, the number of monotonic subgrids in the given grid.

Examples2

Example 1
Input
```
3 3
1 2 5
7 6 4
9 8 3
```
Expected output
```
49
```
Example 2
Input
```
4 3
8 2 5
12 9 6
3 1 10
11 7 4
```
Expected output
```
64
```