#include <bits/stdc++.h>
using namespace std;

const int N = 2005;

int n, m, fa[N], ans1, ans2, siz[N]; 
char a[N][N];

int find_(int x) {
	return x == fa[x] ? x : fa[x] = find_(fa[x]);
}

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n + m; i++)
		fa[i] = i, siz[i] = 1;
	for (int i = 1; i <= n; i++)
		scanf("%s", a[i] + 1);
	a[1][1] = a[n][1] = a[1][m] = a[n][m] = '#';
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			if (a[i][j] == '#') {
				int x = find_(i), y = find_(j + n);
				if (x^y)
					fa[x] = y, siz[y] += siz[x];
			}
	for (int i = 1; i <= n + m; i++)
		if (find_(i) == i)
			ans1 += (i <= n)|(siz[i] >= 2), ans2 += (i > n)|(siz[i] >= 2);
	printf("%d\n", min(ans1, ans2) - 1);
}
#include <bits/stdc++.h>
#define _overload3(_1,_2,_3,name,...)name
#define _rep(i,n)repi(i,0,n)
#define repi(i,a,b)for(int i=int(a),i##_len=(b);i<i##_len;++i)
#define MSVC_UNKO(x)x
#define rep(...)MSVC_UNKO(_overload3(__VA_ARGS__,repi,_rep,_rep)(__VA_ARGS__))
#define all(c)c.begin(),c.end()
#define write(x)cout<<(x)<<'\n'
using namespace std; using ll = long long; template<class T>using vv = vector<vector<T>>;
template<class T>auto vvec(int n, int m, T v) { return vv<T>(n, vector<T>(m, v)); }
constexpr int INF = 1 << 29, MOD = int(1e9) + 7; constexpr ll LINF = 1LL << 60;
struct aaa { aaa() { cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(10); }; }aaaa;

int main() {
    int N, M;
    cin >> N >> M;
    vector<int> X(M), Y(M), Z(M);
    rep(i, M) cin >> X[i] >> Y[i] >> Z[i];

    vv<int> cond(N);
    rep(i, M) {
        cond[X[i] - 1].push_back(i);
    }

    vector<int> xsort(M);
    iota(xsort.begin(), xsort.end(), 0);
    sort(xsort.begin(), xsort.end(), [&](int l, int r) { return X[l] < X[r]; });

    vv<ll> dp = vvec(N + 1, 1 << N, 0LL);
    dp[0][0] = 1;
    rep(i, N) {
        rep(bit, 1 << N) {
            rep(j, N) {
                if (bit >> j & 1) continue;
                int nbit = bit | 1 << j;
                bool ok = true;
                for (int ci : cond[i]) {
                    int y = nbit & ((1 << Y[ci]) - 1);
                    int z = __builtin_popcount(y);
                    if (z > Z[ci]) {
                        ok = false;
                        break;
                    }
                }
                if (ok) {
                    dp[i + 1][nbit] += dp[i][bit];
                }
            }
        }
    }
    write(dp[N][(1 << N) - 1]);
}