#include <bits/stdc++.h>
#define ll long long
#define rep(i,m,n) for(int i=(m); i<=(n); i++)
#define reb(i,m,n) for(int i=(m); i>=(n); i--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define MP make_pair
#define fs first
#define se second
#define bit(msk, i) ((msk >> i) & 1)
#define iter(id, v) for(auto id : v)
#define pb push_back
#define SZ(v) (ll)v.size()
#define ALL(v) v.begin(),v.end()
using namespace std;
mt19937_64 rd(chrono :: steady_clock :: now ().time_since_epoch().count());
ll Rand (ll l, ll r) { return uniform_int_distribution<ll> (l, r) (rd); }
const int N = 4e3 + 7;
const int Mod = 1e9 + 7;///lon
const int INF = 1e9 + 7;
const int BASE = 137;
const int szBL = 350;
int n, m;
int a[N][N];
namespace sub5 {
ll solution() {
vector<vector<int>> toD(n + 1, vector<int> (m + 1, 0)),
toU(n + 1, vector<int> (m + 1, 0)); ///hàng
rep (j, 1, m) {
stack<pii> st;
rep (i, 1, n) {
while (!st.empty() && st.top().fs < a[i][j]) st.pop();
if (!st.empty()) toU[i][j] = st.top().se + 1;
else toU[i][j] = 1;
st.push({a[i][j], i});
}
stack<pii> ().swap(st);
reb (i, n, 1) {
while (!st.empty() && st.top().fs < a[i][j]) st.pop();
if (!st.empty()) toD[i][j] = st.top().se - 1;
else toD[i][j] = n;
st.push({a[i][j], i});
}
}
int res = 0;
vector<int> mxR(n + 3, 0), Down(n + 3, n), Up(n + 3, 1);
rep (j, 1, m) {
rep (i, 1, n)
mxR[i] = 0, Down[i] = n, Up[i] = 1;
reb (k, j - 1, 1) {
int bound = n;
reb (i, n, 1) {
if (Down[i] < bound && Down[i] > i) {
if (Up[Down[i] + 1] <= i + 1) {
++res;
}
}
if (mxR[i] >= min(a[i][j], a[i][k])) {
bound = i;
}
}
bound = 1;
rep (i, 1, n) {
if (Up[i] > bound && Up[i] < i) {
// cout << j <<" "<<k<<" "<<i<<" "<<Up[i] - 1 <<" dasaa\n";
if (Down[Up[i] - 1] >= i) {
++res;
}
}
if (mxR[i] >= min(a[i][j], a[i][k])) {
bound = i;
}
}
///update
rep (i, 1, n) {
mxR[i] = max(mxR[i], a[i][k]);
Down[i] = min(Down[i], toD[i][k]);
Up[i] = max(Up[i], toU[i][k]);
}
}
}
return res;
// cout << res <<"\n";
}
}
namespace sub6 {
bool check () {
rep (i, 1, n)
rep (j, 1, m) if (a[i][j] > 1) return 0;
return 1;
}
///prefix sum
int solution() {
vector<vector<int>> Up(n + 3, vector<int> (m + 3, 0)),
Left (n + 3, vector<int> (m + 3, 0)),
nearbyC(n + 3, vector<int> (m + 3, -1)),///doc
nearbyR(n + 3, vector<int> (m + 3, -1)),///ngang
pre(n + 3, vector<int> (m + 3, 0));
rep (i, 1, n) {
rep (j, 1, m) {
Up[i][j] = a[i - 1][j] == 0 ? i : Up[i - 1][j];
Left[i][j] = a[i][j - 1] == 0 ? j : Left[i][j - 1];
}
}
rep (i, 1, n)
rep (j, 1, m) pre[i][j] = pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1] + a[i][j];
auto getSum = [&] (int x, int y, int u, int v) ->int {
if (x > u || y > v ) return -1;
return pre[u][v] - pre[u][y - 1] - pre[x - 1][v] + pre[x - 1][y - 1];
};
int res = 0;
rep (i, 1, n) {
rep (j, 1, m) {
if (nearbyR[i][j - 1] >= Left[i][j] - 1 && nearbyC[i - 1][j] >= Up[i][j] - 1) {
int u = i, v = j, x = nearbyC[i - 1][j], y = nearbyR[i][j - 1];
// cout << i <<","<<j<<" "<<nearbyC[i - 1][j] <<" "<<nearbyR[i][j - 1]<<" "<<(u - x - 1) * 2 + (v - y + 1) * 2<<"\n";
if (getSum(x + 1, y + 1, u - 1, v - 1) == 0 && getSum(x, y, u, v) - a[u][v] - a[x][v] - a[u][y] - a[x][y] == (u - x - 1) * 2 + (v - y + 1) * 2 - 4) {
++res;
}
}
nearbyR[i][j] = (a[i - 1][j] == 1) ? j : nearbyR[i][j - 1];
nearbyC[i][j] = (a[i][j - 1] == 1) ? i : nearbyC[i - 1][j];
}
}
// cout << res <<"\n";
return res;
}
}
ll count_rectangles (vector<vector<int>> A) {
n = SZ(A);
m = SZ(A[0]);
rep (i, 1, n)
rep (j, 1, m) a[i][j] = A[i - 1][j - 1];
if (n * m <= 490000)
return sub5 :: solution();
else if (sub6 :: check())
return sub6 :: solution();
}
void solution () {
// cout << count_rectangles({{4, 8, 7, 5, 6},
// {7, 4, 10, 3, 5},
// {9, 7, 20, 14, 2},
// {9, 14, 7, 3, 6},
// {5, 7, 5, 2, 7},
// {4, 5, 13, 5, 6}});
// return;
cin >> n >> m;
rep (i, 1, n)
rep (j, 1, m) cin >> a[i][j];
// if (n * m <= 490000)
// cout << sub5 :: solution() <<"\n";
cout << sub6 :: solution() <<"\n";
}
//#define file(name) freopen(name".inp","r",stdin); freopen(name".out","w",stdout);
//main () {
// file("c");
// ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0);
// int num_Test = 1;
//// cin >> num_Test;
// while (num_Test--)
// solution();
//}
/*
no bug challenge +20
gọi sao cho có lợi cho mình nhất
*/
