1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int INF=1e9+7, LIM=1e5+7, N=18;
string S[N];
int odw[N], skok[N][LIM], prawo[N][LIM], lewo[N+1][LIM], sum[LIM], L, n, x, y;
int nxt(int p, int k) {
	if(S[k][p/y]=='.') {
		if(prawo[k][p/y]*y-(p%y)>=x) return p;
	}
	if(p/y+1>=L) return INF;
	return skok[k][p/y+1];
}
int prv(int l, int r, int k) {
	if(l>r) return -1;
	if(lewo[k][r/y]<l/y) return -1;
	return min((lewo[k][r/y]+1)*y, r+1);
}
bool check(vector<int>&V) {
	if(V.size()==n) return true;
	int pocz=0;
	if(V.size()) {
		pocz=V.back();
		int lst=V.back();
		rep(i, V.size()) {
			if(V[i]+x>lst) {
				pocz=max(pocz, prv(lst, V[i]+x-1, (int)V.size()-i+1));
				lst=V[i]+x;
			}
		}
	}
	pair<int,int>mi1={INF, INF}, mi2={INF, INF};
	rep(i, n) if(!odw[i]) {
		int a=nxt(pocz, i);
		if(a!=INF) {
			pair<int,int>p={a, i};
			if(p<=mi1) {
				mi2=mi1;
				mi1=p;
			} else mi2=min(mi2, p);
		}
	}
	if(mi1.st<INF) {
		V.pb(mi1.st);
		odw[mi1.nd]=1;
		if(check(V)) return true;
		odw[mi1.nd]=0;
		V.pop_back();
	}
	if(mi2.st<INF) {
		V.pb(mi2.st);
		odw[mi2.nd]=1;
		if(check(V)) return true;
		odw[mi2.nd]=0;
		V.pop_back();
	}
	return false;
}
bool czy() {
	rep(i, n) {
		skok[i][L]=INF;
		for(int j=L-1; j>=0; --j) {
			skok[i][j]=skok[i][j+1];
			if(prawo[i][j]*y>=x) skok[i][j]=j*y;
		}
		odw[i]=0;
	}
	vector<int>V;
	return check(V);
}
bool srt(pair<ll,ll>a, pair<ll,ll>b) {
	return a.st*b.nd<b.st*a.nd;
}
void solve() {
	cin >> n >> L;
	rep(i, n) cin >> S[i];
	rep(i, L) sum[i]=0;
	rep(i, n) rep(j, L) if(S[i][j]=='.') ++sum[j];
	rep(i, L) if(!sum[i]) {
		cout << -1 << '\n';
		return;
	}
	rep(i, n) {
		rep(j, L+1) prawo[i][j]=0;
		for(int j=L-1; j>=0; --j) if(S[i][j]=='.' && sum[j]>1) prawo[i][j]=prawo[i][j+1]+1;
	}
	rep(i, n+1) {
		rep(j, L) lewo[i][j]=-1;
		rep(j, L) {
			if(j) lewo[i][j]=lewo[i][j-1];
			if(sum[j]<=i) lewo[i][j]=j;
		}
	}
	int po=0, ko=L;
	while(po<ko) {
		int sr=(po+ko+1)/2;
		x=sr; y=1;
		if(czy()) po=sr; else ko=sr-1;
	}
	vector<pair<ll,ll>>U;
	U.pb({0, 1});
	for(int i=2; i<=n; ++i) {
		for(int j=1; j<i; ++j) if(gcd(i, j)==1) U.pb({j, i});
	}
	sort(all(U), srt);
	int calk=po;
	po=0; ko=(int)U.size()-1;
	while(po<ko) {
		int sr=(po+ko+1)/2;
		y=U[sr].nd;
		x=calk*y+U[sr].st;
		if(czy()) po=sr; else ko=sr-1;
	}
	y=U[po].nd;
	x=calk*y+U[po].st;
	cout << x << "/" << y << '\n';
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int _=1;
//	cin >> _;
	while(_--) solve();
}