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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
int n,m;
int a[100005];
int busy[19][100005];//latest moment<=j where at most i people are available

int nxt[19][100005];//next work
int nxtgd[19][100005];//next sleeping window start >= i*den


int wake[19];
bool died[19];
int plan[19];
int ord[19];
int num,den;


bool win(int slept){
	if(slept==n-1) return true;
	int opt1=0,opt2=0,opt3=0;
	for(int i=1; i<=n ;i++){
		if(died[i]) continue;
		if(opt3==0 || plan[opt3]>plan[i]) opt3=i;
		if(opt2==0 || plan[opt2]>plan[opt3]) swap(opt2,opt3);
		if(opt1==0 || plan[opt1]>plan[opt2]) swap(opt1,opt2);
	}
	++slept;
	auto test=[&](int opt1,array<int,2>fix) ->bool{//test sending opt1 to sleep
		//cout << "test " << slept << ' ' << opt1 << endl;
		ord[slept]=opt1;
		died[opt1]=true;
		wake[opt1]=plan[opt1]+num;
		bool ok=true;
		array<int,2>oldp;
		for(int j=0; j<2 ;j++){
			int opt2=fix[j];
			if(opt2==0) continue;
			oldp[j]=plan[opt2];
			plan[opt2]=max(plan[opt2],plan[opt1]);
			for(int i=1; i<=slept ;i++){
				if(wake[ord[i]]<=plan[opt2]) continue;
				int b=min(busy[slept-i+2][(wake[ord[i]]+den-1)/den]*den,wake[ord[i]]);
				plan[opt2]=max(plan[opt2],b);
			}
			int work=nxt[opt2][plan[opt2]/den];
			if(work-plan[opt2]<num){
				if(plan[opt2]/den<m) plan[opt2]=nxtgd[opt2][plan[opt2]/den+1];
				else plan[opt2]=1e9;
			}
			if(plan[opt2]==1e9) ok=false;
		}
		//recal plan[opt2]
		if(ok)
			if(win(slept)) return true;
		for(int j=0; j<2 ;j++){
			plan[fix[j]]=oldp[j];
		}
		died[opt1]=false;
		return false;
	};
	if(test(opt1,{opt2,0})) return true;
	if(test(opt2,{opt1,opt3})) return true;
	return false;
}
bool check(int Gnum,int Gden){
	//cout << "check " << Gnum << ' ' << Gden << endl;
	num=Gnum,den=Gden;
	for(int i=1; i<=n ;i++){
		nxt[i][m]=m*den;
		nxtgd[i][m]=1e9;
		for(int j=m-1; j>=0 ;j--){
			nxt[i][j]=nxt[i][j+1];
			if(a[j+1]==(1<<i) || ((a[j+1]>>i)&1)==0) nxt[i][j]=j*den;
			nxtgd[i][j]=nxtgd[i][j+1];
			if(nxt[i][j]-j*den>=num) nxtgd[i][j]=j*den;
		}
		died[i]=false;
		plan[i]=nxtgd[i][0];
		if(plan[i]==1e9) return false;
	}
	if(win(0)) return true;
	else return false;
}
pair<int,int>get(int mid){//closest fraction >= mid/n^2 with den<=n
	int num=(mid+n*n-1)/(n*n),den=1;
	for(int i=2; i<=n ;i++){
		int c=(mid*i+n*n-1)/(n*n);
		int d=i;
		if(num*d>c*den){
			num=c;
			den=d;
		}
	}
	//cout << "! " << num << ' ' << den << endl;
	return {num,den};
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	cin >> n >> m;
	for(int i=1; i<=n ;i++){
		for(int j=1; j<=m ;j++){
			char c;cin >> c;
			if(c=='.') a[j]|=1<<i;
		}
	}
	for(int i=1; i<=m ;i++) if(a[i]==0) return cout << "-1\n",0;
	for(int i=1; i<=n ;i++){
		busy[i][0]=0;
		for(int j=1; j<=m ;j++){
			busy[i][j]=busy[i][j-1];
			if(__builtin_popcount(a[j])<=i) busy[i][j]=j;
		}
	}
	int l=0,r=m*n*n;
	while(l!=r){
		int mid=(l+r+1)/2;
		auto ratio=get(mid);
		if(check(ratio.fi,ratio.se)) l=mid;
		else r=mid-1;
	}
	auto ratio=get(l);
	cout << ratio.fi << '/' << ratio.se << '\n';
}