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
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define deb(...)
#define DBP(...)
using namespace std;
using   ll         = long long;
using   vi         = vector<int>;
using   pii        = pair<int, int>;
#define pb           push_back
#define mp           make_pair
#define x            first
#define y            second
#define rep(i, b, e) for (int i = (b); i < (e); i++)
#define each(a, x)   for (auto& a : (x))
#define all(x)       (x).begin(), (x).end()
#define sz(x)        int((x).size())

void run();

int main() {
	cin.sync_with_stdio(0); cin.tie(0);
	cout << fixed << setprecision(12);
	run();
	cout << flush; _Exit(0);
}

#define ends ends__

constexpr int MAX_N = 18;
constexpr int MAX_L = 100'005;
constexpr ll SCALE = 232792560; // lcm(1,...,20)

int n, len;
bool avail[MAX_L][MAX_N];
int numAvail[MAX_L];
int prevAvail[MAX_L][MAX_N+1];
int firstFit[MAX_L][MAX_N];

ll ends[MAX_N];
int endsCeil[MAX_N];
bool used[MAX_N];

bool solve(int numUsed, ll start, ll seg) {
	if (numUsed >= n) return 1;

	rep(i, 0, numUsed) {
		int j = prevAvail[endsCeil[i]][numUsed-i+1] + 1;
		start = max(start, min(j*SCALE, ends[i]));
	}

	if (start > len*SCALE-seg) return 0;

	int startFloor = int(start/SCALE), leftover = int((start+seg-1)/SCALE);
	pii opt1 = {INT_MAX, -1}, opt2 = {INT_MAX, -1};

	rep(i, 0, n) if (!used[i]) {
		int p = firstFit[startFloor][i];
		if (p == startFloor && (!avail[leftover][i] || numAvail[leftover] == 1)) {
			p = firstFit[startFloor+1][i];
		}
		if (p == -1) {
			return 0;
		}
		if (p <= opt1.x) {
			opt2 = opt1;
			opt1 = {p, i};
		} else if (p < opt2.x) {
			opt2 = {p, i};
		}
	}

	for (auto [posFloor, index] : {opt1, opt2}) {
		if (index != -1) {
			ll pos = max(posFloor*SCALE, start);
			ends[numUsed] = pos + seg;
			endsCeil[numUsed] = int((ends[numUsed]+SCALE-1) / SCALE);
			used[index] = 1;
			if (solve(numUsed+1, pos, seg)) return 1;
			used[index] = 0;
		}
	}

	return 0;
}

bool check(ll seg) {
	int lastBusy[MAX_N];
	fill(firstFit[len], firstFit[len]+n, -1);
	fill(lastBusy, lastBusy+n, len);
	for (int i = len-1; i >= 0; i--) {
		rep(j, 0, n) {
			if (!avail[i][j] || numAvail[i] == 1) lastBusy[j] = i;
			firstFit[i][j] = ((lastBusy[j]-i)*SCALE >= seg ? i : firstFit[i+1][j]);
		}
	}
	fill(used, used+n, 0);
	return solve(0, 0, seg);
}

void run() {
	string tmp;
	cin >> n >> len;
	rep(i, 0, n) {
		cin >> tmp;
		rep(j, 0, len) avail[j][i] = (tmp[j] == '.');
		avail[len][i] = 0;
	}

	fill(prevAvail[0], prevAvail[0]+n+1, -1);
	rep(i, 0, len) {
		numAvail[i] = accumulate(avail[i], avail[i]+n, 0);
		if (numAvail[i] == 0) {
			cout << "-1\n";
			return;
		}
		copy(prevAvail[i], prevAvail[i]+n+1, prevAvail[i+1]);
		prevAvail[i+1][numAvail[i]] = i;
	}

	ll begin = 0, end = len*SCALE+1;
	while (begin+1 < end) {
		ll mid = (begin+end) / 2;
		(check(mid) ? begin : end) = mid;
	}

	ll g = gcd(begin, SCALE);
	cout << begin/g << '/' << SCALE/g << '\n';
}