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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
#include <bits/stdc++.h>
using namespace std;
#define fwd(i, a, n) for (int i = (a); i < (n); i++)
#define rep(i, n)    fwd(i, 0, n)
#define all(X)       X.begin(), X.end()
#define sz(X)        int(size(X))
#define pb           push_back
#define eb           emplace_back
#define st           first
#define nd           second
using pii = pair<int, int>;
using vi = vector<int>;
using ll = long long;
using ld = long double;
#ifdef LOC
auto SS = signal(6, [](int) {
	*(int *)0 = 0;
});
#	define DTP(x, y)                                      \
		auto operator<<(auto &o, auto a)->decltype(y, o) { \
			o << "(";                                      \
			x;                                             \
			return o << ")";                               \
		}
DTP(o << a.st << ", " << a.nd, a.nd);
DTP(for (auto i : a) o << i << ", ", all(a));
void dump(auto... x) {
	((cerr << x << ", "), ...) << '\n';
}
#	define deb(x...) cerr << setw(4) << __LINE__ << ":[" #x "]: ", dump(x)
#else
#	define deb(...) 0
#endif

struct fraction {
	int num, den;
	fraction(int n, int d) : num(n), den(d) {
		int g = __gcd(num, den);
		num /= g;
		den /= g;
	}
	bool operator<(const fraction &f) const {
		return 1ll * num * f.den < 1ll * f.num * den;
	}
	bool operator==(const fraction &f) const {
		return num == f.num && den == f.den;
	}
};

constexpr int max_n = 18;
constexpr int max_m = 100 * 1000;
int dp[(1 << max_n)][max_n];

int n, m;

constexpr int inf = 1e8;

bitset<max_m> a[max_n];

vi load;

int last_load_geq[max_m][max_n];

// Stuff for scaled grid
int unit_length = 0, seg_length = 0;

pii first_dp[max_n][max_m + 1];

int m_scaled;

void prep_scaled_grid(const fraction &f) {
	// Length of one tile in scaled grid
	unit_length = f.den;
	// Length of one segment in scaled grid
	seg_length = f.num;

	m_scaled = m * unit_length;
	// Fill first_dp
	rep(row, n) {
		int next_nonempty = m;
		first_dp[row][m] = {inf * unit_length, inf * unit_length};
		for (int col = m - 1; col >= 0; col--) {
			if (a[row][col] || load[col] == n - 1)
				next_nonempty = col;
			first_dp[row][col] = first_dp[row][col + 1];
			if (unit_length * (next_nonempty - col) >= seg_length)
				first_dp[row][col] = {
					col * unit_length, next_nonempty * unit_length};
		}
	}
}

int seg_set_earliest(int *ptr, int k) {
	int earliest = 0;
	if (k > 0)
		earliest = ptr[0] - seg_length;
	rep(i, k) {
		int seg_end = ptr[i];
		int seg_end_block = (seg_end - 1) / unit_length;
		int overloaded_pos = last_load_geq[seg_end_block][n - 2 - i];
		int overloaded_pos_end = unit_length * (overloaded_pos + 1);
		earliest = max(earliest, min(seg_end, overloaded_pos_end));
	}
	return earliest;
}

int temp[max_n];

// PROSZE ZADZIALAJ GLUPTASIE JEDEN <3 <3 <3 ! ! !
bool ok_heuristic() {
	int reversed_inf = __builtin_bswap32(inf);
	fwd(mask, 1, 1 << n) fill(dp[mask], dp[mask] + n, reversed_inf);
	rep(mask, (1 << n) - 1) {
		int mask_size = __builtin_popcount(mask);
		if (mask_size > 0 && dp[mask][n - 1] == reversed_inf)
			continue;
		rep(i, mask_size) temp[i] =
			__builtin_bswap32(dp[mask][n - mask_size + i]);
		int earliest = seg_set_earliest(temp, mask_size);
		int pos_p = earliest / unit_length;
		if (pos_p >= m)
			continue;
		rep(to_add, n) if (!(mask & (1 << to_add))) {
			auto [new_seg_end, R] = first_dp[to_add][pos_p];
			new_seg_end = max(new_seg_end, earliest);
			if (new_seg_end + seg_length > R)
				new_seg_end = first_dp[to_add][pos_p + 1].st;
			if (new_seg_end == inf)
				continue;
			new_seg_end += seg_length;
			int new_mask = mask | (1 << to_add);
			dp[mask][n - mask_size - 1] = __builtin_bswap32(new_seg_end);
			int new_size = mask_size + 1;
			int new_size_off = n - new_size;
			bool better = memcmp(
							  dp[new_mask] + new_size_off,
							  dp[mask] + new_size_off,
							  new_size * sizeof(int)) > 0;
			if (better) {
				memcpy(
					dp[new_mask] + new_size_off,
					dp[mask] + new_size_off,
					new_size * sizeof(int));
			}
		}
	}
	return dp[(1 << n) - 1][0] != reversed_inf;
}

void sol() {
	cin >> n >> m;
	string s;
	rep(i, n) {
		cin >> s;
		rep(j, m) a[i][j] = (s[j] == 'X') ? 1 : 0;
	}

	load = vi(m);

	rep(i, n) load[0] += a[i][0];

	if (load[0] == n) {
		cout << "-1\n";
		return;
	}

	rep(i, n) if (load[0] >= i) last_load_geq[0][i] = 0;
	else last_load_geq[0][i] = -1;

	fwd(j, 1, m) {
		rep(i, n) {
			load[j] += a[i][j];
			last_load_geq[j][i] = last_load_geq[j - 1][i];
		}
		if (load[j] == n) {
			cout << "-1\n";
			return;
		}
		rep(i, load[j] + 1) last_load_geq[j][i] = j;
	}

	if (n == 1) {
		cout << "0/1\n";
		return;
	}
	// Possible and N >= 2

	// Go from fractions to scaled grid in order to operate on integers
	auto ok = [&](const fraction &f) -> bool {
		prep_scaled_grid(f);
		return ok_heuristic();
	};

	vector<fraction> fractions;
	fwd(num, 1, m + 1) fwd(den, 1, n + 1) fractions.pb(fraction(num, den));
	sort(all(fractions));
	fractions.erase(unique(all(fractions)), fractions.end());
	fraction best(0, 1);
	int L = 0, R = sz(fractions);
	while (L < R) {
		int M = (L + R) / 2;
		fraction f = fractions[M];
		if (ok(f)) {
			best = f;
			L = M + 1;
		} else {
			R = M;
		}
	}
	cout << best.num << '/' << best.den << '\n';
}

int32_t main() {
	cin.tie(0)->sync_with_stdio(0);
	cout << fixed << setprecision(10);
	sol();
#ifdef LOCF
	cout.flush();
	cerr << "- - - - - - - - -\n";
	(void)!system(
		"grep VmPeak /proc/$PPID/status | sed s/....kB/\' MB\'/1 >&2"); // 4x.kB
																		// ....kB
#endif
}