#include<iostream>
#include<set>
#include<vector>
using namespace std;
typedef long long li;
#define rep(i,n) for(int i=0;i<(n);i++)
#define df 0
template<class T> void print(const T& t){ cout << t << "\n"; }
template<class T, class... Ts> void print(const T& t, const Ts&... ts) { cout << t; if (sizeof...(ts)) cout << " "; print(ts...); }

int find(int a,vector<int>& uf){
  if(uf[a]<0) return a;
  return uf[a]=find(uf[a],uf);
}

void unite(int a,int b,vector<int>& uf){
  a=find(a,uf),b=find(b,uf);
  if(a==b)return ;
  if(uf[a]>uf[b]) swap(a,b);
  uf[a]+=uf[b];
  uf[b]=a;
}

int main(){
  int h,w; cin >>h >>w;
  vector<string> mp(h); rep(i,h) cin >>mp[i];
  vector<vector<int>> adj(h+w);
  int n=h+w;
  vector<int> uf(n,-1);
  unite(0,h,uf);
  unite(h-1,h,uf);
  unite(h-1,h+w-1,uf);
  unite(0,h+w-1,uf);
  rep(i,h) rep(j,w){
    if(mp[i][j]=='#'){
      unite(i,h+j,uf);
    }
  }
  
  set<int> tate,yoko;
  rep(i,h){
    tate.insert(find(i,uf));
  }
  rep(j,w){
    yoko.insert(find(h+j,uf));
  }
  print(min(tate.size(),yoko.size())-1);
}

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std;
void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     @hamayanhamayan0
　　　　／　　　＼　 　  |　|
　　　 /　　 /￣￣￣￣/　　|
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿
　 　　　＼/＿＿＿＿/　（u　⊃
---------------------------------------------------------------------------------------------------*/
 
 
 
 
 
 
 
 
 
 
 
 
 
 
int N, M;
ll dp[1 << 18];
vector<pair<int, int>> restrictions[18];
//---------------------------------------------------------------------------------------------------
int tot[19];
bool check(int msk) {
	int cnt = 0;
	rep(i, 1, N + 1) tot[i] = 0;
	rep(i, 0, N) if (msk & (1 << i)) {
		tot[i + 1]++;
		cnt++;
	}
	rep(i, 2, N + 1) tot[i] += tot[i - 1];
	
	fore(p, restrictions[cnt]) if (p.second < tot[p.first]) return false;
	return true;
}
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> N >> M;
	rep(i, 0, M) {
		int X, Y, Z; cin >> X >> Y >> Z;
		restrictions[X].push_back({ Y, Z });
	}
 
	dp[0] = 1;
	rep(msk, 0, 1 << N) rep(nxt, 0, N) if (!(msk & (1 << nxt))) {
		if (check(msk + (1 << nxt))) dp[msk + (1 << nxt)] += dp[msk];
	}
	cout << dp[(1 << N) - 1] << endl;
}
 