주차 이론

주차장은 $n \times m$ 개의 주차 공간으로 이루어진 직사각형이다. 주차장의 각 행과 각 열의 양 끝에는 입구가 있다.

주차장은 가득 차 있으며, 각 주차 공간에는 그 자리에 주차한 차가 들어온 순서가 주어진다. 1번은 가장 먼저 들어온 차이고, $n \cdot m$번은 가장 마지막에 들어온 차이다.

Abolfazl은 차가 주차장에 들어오는 방식에 관한 이론을 세웠다. 특정 방향(행 또는 열)으로 들어온 차는 주차 자리를 찾을 때까지 직진하며, 방향을 바꾸지 않는다. 또한 차는 이미 차가 주차되어 있는 칸을 지나갈 수 없다.

Abolfazl은 주차장에서 부분 격자를 골라, 이 규칙을 만족하는 부분 격자의 개수를 세고 싶어 한다. 부분 격자 안에 있는 차들만 고려한다. 그 안의 모든 차가 위의 규칙을 어기지 않고 주차할 수 있으면 그 부분 격자는 유효하다. 유효한 부분 격자의 개수를 구하라.

첫째 줄에 주차장의 행의 수 $n$과 열의 수 $m$이 주어진다. $1 \le n, m \le 500$이다. 이어서 $n$개의 줄에 각각 $m$개의 정수가 주어지며, 각 줄은 해당 행에 들어온 차의 순서를 나타낸다. 주어지는 모든 수는 $1$부터 $n \cdot m$까지의 서로 다른 값이다.

유효한 부분 격자의 개수를 한 줄에 출력한다.