Cho bảng kích thước ~n \times m~, ô ở hàng ~i~, cột ~j~ có chứa số nguyên dương ~a_{i, j}~. Trên bảng, bạn chỉ có thể di chuyển xuống dưới hoặc sang phải.

Xét một cặp số ~(l, r)~. Khi đó, cặp số ~(l, r)~ được gọi là hợp lệ nếu: chỉ xét các ô có chứa giá trị trong đoạn ~[l, r]~, bạn có thể sử dụng các ô đó để di chuyển từ ô ~(1, 1)~ tới ô ~(n, m)~.

Ví dụ:

• Xét bảng sau:

1 2 3
3 2 1

• ~(1, 2)~ là một cặp số hợp lệ vì ta có thể di chuyển như sau: ~(1, 1) - (1, 2) - (2, 2) - (3, 2)~.
• ~(2, 3)~ không là cặp số hợp lệ vì ta không thể di chuyển.

Hãy đếm số lượng cặp số ~(l, r)~, thỏa mãn ~1 \le l \le r \le max (a)~, và cặp số đó là hợp lệ. ~max (a)~ ở đây là giá trị tối đa trên bảng ~a~.

Input

Dòng đầu tiên chứa hai số nguyên dương ~n, m~ (~1 \le n \le 5~, ~1 \le m \le 10^5~) mô tả kích thước bảng.

~n~ dòng tiếp theo, mỗi dòng gồm ~m~ số nguyên dương ~a_{i, j}~ (~1 \le a_{i, j} \le 10^9~) mô tả một ô trên bảng.

Output

In ra số cặp số thỏa mãn điều kiện.

Sample Input

2 3
1 2 3
3 2 1

Sample Output

2

Hai cặp số thỏa mãn là ~(1, 2)~ và ~(1, 3)~.