단조성

시간 제한5초메모리 제한512 MB

요약

모든 값이 서로 다른 r×c 격자에서, 각 행과 각 열이 증가하거나 감소하는 부분격자의 개수를 구합니다.

난이도: 어려움10점 중 8점
유형: 행렬, 동적 계획법, 조합론
정답자: 아직 제출이 없습니다

문제

r행 c열 격자의 각 칸에는 1 이상 $r \times c$ 이하의 정수가 하나씩 적혀 있으며, 모든 칸의 수는 서로 다르다.

각 행과 각 열이 증가하거나 감소하면 이 격자를 단조 격자라고 한다. 행마다, 열마다 증가와 감소 방향은 달라도 된다.

부분 격자는 다음과 같이 만든다. 먼저 공집합이 아닌 행의 부분집합과 공집합이 아닌 열의 부분집합을 고른다. 그다음 선택한 행과 선택한 열이 만나는 칸의 수를 원래 격자에서의 순서대로 가져온다.

이 격자에는 $(2r-1)(2c-1)$ 개의 공집합이 아닌 부분 격자가 있다. 이 중 단조 격자인 것의 개수를 구하라.

다음 격자를 보자.

1 2 5
7 6 4
9 8 3

1×1 부분 격자가 9개, 1×2가 9개, 1×3이 3개, 2×1이 9개, 2×2가 9개, 2×3이 3개, 3×1이 3개, 3×2가 3개, 3×3이 1개 있으며 모두 단조 격자이므로 답은 49이다.

입력

각 테스트 케이스는 공백으로 구분된 두 정수 $r$ 과 $c$ 가 적힌 줄로 시작한다 ( $1 \le r, c \le 20$ ). 이어지는 $r$ 개의 줄에는 공백으로 구분된 정수 $x$ 가 각각 $c$ 개씩 적혀 있으며, 이것이 격자이다 ( $1 \le x \le r \times c$ , 모든 $x$ 는 서로 다르다).

출력

주어진 격자에서 단조 부분 격자의 개수를 정수 하나로 출력한다.

예제2

예제 1
입력
```
3 3
1 2 5
7 6 4
9 8 3
```
예상 출력
```
49
```
예제 2
입력
```
4 3
8 2 5
12 9 6
3 1 10
11 7 4
```
예상 출력
```
64
```